# IMU Preintegrated Features for Efficient Deep Inertial Odometry

Rooholla Khorrambakht  K.N.Toosi University of TechnologyTehranIran
<EMAIL_ADDRESS>,  Hamed Damirchi  K.N.Toosi University of
TechnologyTehranIran<EMAIL_ADDRESS>and  Hamid D. Taghirad
K.N.Toosi University of TechnologyTehranIran<EMAIL_ADDRESS>
(2022)

###### Abstract.

MEMS Inertial Measurement Units (IMUs) as ubiquitous proprioceptive motion
measurement devices are available on various everyday gadgets and robotic
platforms. Nevertheless, the direct inference of geometrical transformations
or odometry based on these data alone is a challenging task. This is due to
the hard-to-model imperfections and high noise characteristics of the sensor,
which has motivated research in formulating the system as an end-to-end
learning problem, where the motion patterns of the agent are exploited to
facilitate better odometry estimates. However, this benefit comes at the cost
of high computation and memory requirements, which makes deep inertial
odometry unsuitable for low-power and edge applications. This paper attempts
to address this conflict by proposing the IMU preintegrated features as a
replacement for the raw IMU data in deep inertial odometry. Exploiting the
manifold structure of the IMU motion model, these features provide a
temporally compressed motion representation that preserves important
geometrical information. We demonstrate the effectiveness and efficiency of
this approach for the task of inertial odometry on two applications of
pedestrian motion estimation and autonomous vehicles. We show a performance
improvement compared to raw inputs while reducing the computational burdens.
Additionally, we demonstrate the efficiency of this approach through an
embedded implementation on a resource-constrained microcontroller.

IMU preintegration, deep inertial odometry, autonomous vehicles, pedestrian
tracking

††copyright: rightsretained††journalyear: 2022

##  1\. Introduction

With the advent of MEMS Inertial Measurement Units (IMUs) as low-power and
low-cost proprioceptive motion sensors, this modality has been added to
numerous everyday gadgets and autonomous systems. Smartphones and
smartwatches, autonomous vehicles, VR111Virtual Reality headsets, and even
gaming consoles all contain some variant of this sensor. This widespread
availability of this modality has encouraged new applications such as user
activity recognition (Damirchi et al., 2020) and pedestrian tracking (Chen et
al., 2020) for situations where other sensors may fail.

However, the expense of their lower cost and smaller form factor, is that MEMS
IMUs are much more challenging to model accurately due to the manufacturing
imperfections, high and time-variant noise characteristics, and nonlinear
effects. While many prominent classical pipelines based on statistical sensor
fusion and optimization systems already exist for the efficient incorporation
of IMUs into various applications (Sandy et al., 2019; Huang, 2019), there are
many scenarios where the restricting assumptions of the system’s formulation
limit the application and robustness of the method.

These challenges have encouraged researchers to consider deep learning methods
to enable previously implausible applications of this modality as independent
sensors. The ability to learn high-dimensional latent presentations from data
enables these methods to exploit the underlying motion patterns of the agent
to reduce the odometry drift.

Generally, there are two lines of research in this field. Many works try to
exploit leaned models as modules within a classical fusion system to detect
important motion events. For instance, (Wagstaff et al., 2020) proposes using
an LSTM to detect zero-velocity events in human walking to reset the states of
an Extended Kalman Filter (EKF) and avoid the accumulation of error. In a
similar attempt, (Brossard et al., 2019) designs a classifier that detects
specific motion modes of a wheeled vehicle and uses the classifier’s results
to define a set of pseudo measurements for an Invariant Extended Kalman
Filter.

On the other hand, the opposing approach is to cast the problem as a pure
data-driven pipeline and synthesize models that directly consume raw sensor
data to yield the final prediction. For instance, (Chen et al., 2018a)
proposes using an LSTM model for predicting the human trajectory represented
in polar coordinates. Furthermore, this end-to-end application of IMUs has
also been considered alongside other modalities such as vision (Chen et al.,
2019a; Almalioglu et al., 2019), and thermal images (Saputra et al., 2020) to
estimate the ego-motion of a robot or autonomous vehicle.

While the former approaches are computationally efficient due to their
classical core and minimal models, they are highly limited to the design
domain for which they are engineered. On the other hand, even though the data-
driven methods are highly flexible and general, they lack the computational
efficiency of their classical counterparts, and they may not be easily used
for low-power embedded and wearable applications.

This paper aims to address this conflict by proposing an efficient and
temporally compact motion representation that draws inspiration from the
preintegration theory known to the graph-based Visual-Inertial Odometry (VIO)
community (Forster et al., 2017). While (Forster et al., 2017) formulates the
preintegration as part of a classical VIO optimization problem and as a motion
constraint, the novelty of this approach is in the repurposing of this
geometrical constraint as a preprocessing/input-feature for learning-based
models. This input feature replaces the raw IMU data and in doing so, improves
the performance while extensively reducing the computational burdens. Finally,
the efficiency of this approach has been further illustrated by providing an
embedded implementation of a deep pedestrian inertial odometry pipeline on a
microcontroller with highly restricted resources.

The rest of this paper is organized as follows. Section 2 introduces the
Preitegrated features and describes the baseline models and the training
procedure used to demonstrate the effectiveness of the proposed approach.
Then, Section 3 presents the experimental setups and the results of applying
preintegration for the two tasks of pedestrian and autonomous vehicles
inertial odometry. Furthermore, this section also demonstrates the
computational efficiency of the approach through the embedded implementation
of IO-Net (Chen et al., 2020) with preintegrated IMU inputs, and finally,
Section 4 concludes the paper and proposes future directions.

##  2\. Methodology

This section introduces the methodology for extraction of preintegrated
features from IMU raw data and presents the baseline architecture and training
procedure used to demonstrate their application in deep inertial odometry.

Figure 1. The baseline model for investigating the effectiveness of
preintegrated features.

###  2.1. IMU Preintegrated Features

Preintegrated IMU features draw inspiration from the factor graph approach to
Visual Inertial Odometry (VIO) (Forster et al., 2017). Factor graphs are
Probabilistic Graphical Models (PGM) that provide a natural language to
describe many optimization problems in robotics and SLAM222Simultaneous
Localization and Mapping (Dellaert, 2021). In this formulation, the IMU
constrains the motion in between keyframes based on linearization-point
independent energy factors formulated using the kinematic measurement model of
an IMU (Forster et al., 2017):

(1) $\displaystyle\mathbf{R_{n+1}}$
$\displaystyle=\mathbf{R_{n}}\exp((\mathbf{\tilde{\boldsymbol{\omega}}_{n}}-\mathbf{b_{g}}-\boldsymbol{\eta_{g}})^{\wedge}\Delta
t)$ $\displaystyle\mathbf{v_{n+1}}$
$\displaystyle=\mathbf{v_{n}}+\mathbf{g}\Delta
t+\mathbf{R_{n}}(\mathbf{\tilde{a}_{n}}-\mathbf{b_{a}}-\boldsymbol{\eta_{a}})$
$\displaystyle\mathbf{p_{n+1}}$
$\displaystyle=\mathbf{p_{n}}+\mathbf{v_{n}}\Delta
t+\frac{1}{2}\mathbf{g}\Delta
t^{2}+\mathbf{R_{n}}(\mathbf{\tilde{a}_{n}}-\mathbf{b_{a}}-\boldsymbol{\eta_{a}})\Delta
t^{2}$

where $\mathbf{R_{n}}$, $\mathbf{v_{n}}$, and $\mathbf{p_{n}}$ are
orientation, velocity and position of the sensor with respect to the world
frame, and $\Delta t$ is the sampling time of the IMU. The angular velocity
and acceleration measurements
$\boldsymbol{\tilde{\omega}_{n}},\boldsymbol{\tilde{a}_{n}}$ from the
gyroscope and accelerator are contaminated with additive Gaussian noise
$\boldsymbol{\eta_{g}},\boldsymbol{\eta_{a}}$ and random walk bias terms
$\boldsymbol{b_{g}},\boldsymbol{b_{a}}$. Furthermore, the $\exp(\cdot)$ is the
SO3 exponential map that links lie algebra $\mathfrak{so}(3)$ vectors to their
corresponding SO3 matrices.

Batches of IMU measurements between two $\mathrm{i}$ and $\mathrm{j}$
keyframes may be compressed into motion constraints by integrating the above
equations. Nevertheless, the outcome of this integration changes with the
initial condition at time $i$. Multiplying both sides of this integration by
$\mathrm{R_{i}}$ breaks this dependence and yields the following initial
conditions independent constraints (Forster et al., 2017):

(2) $\displaystyle\Delta\mathbf{R}_{ij}$
$\displaystyle\triangleq\mathbf{R}_{i}^{\top}\mathbf{R}_{j}=\prod_{k=i}^{\jmath-1}\exp\left(\left(\tilde{\boldsymbol{\omega}}_{k}-\mathbf{b}_{k}^{g}-\boldsymbol{\eta}_{k}^{g}\right)\Delta
t\right)$ $\displaystyle\Delta\mathbf{v}_{ij}$
$\displaystyle\triangleq\mathbf{R}_{i}^{\top}\left(\mathbf{v}_{j}-\mathbf{v}_{i}-\mathbf{g}\Delta
t_{ij}\right)$
$\displaystyle=\sum_{k=i}^{j-1}\Delta\mathbf{R}_{ik}\left(\tilde{\mathbf{a}}_{k}-\mathbf{b}_{k}^{a}-\boldsymbol{\eta}_{k}^{a}\right)\Delta
t$ $\displaystyle\Delta\mathbf{p}_{ij}$
$\displaystyle\triangleq\mathbf{R}_{i}^{\top}\left(\mathbf{p}_{j}-\mathbf{p}_{i}-\mathbf{v}_{i}\Delta
t_{ij}-\frac{1}{2}\sum_{k=i}^{j-1}\mathbf{g}\Delta t^{2}\right)$
$\displaystyle=\sum_{k=i}^{j-1}\left[\Delta\mathbf{v}_{ik}\Delta
t+\frac{1}{2}\Delta\mathbf{R}_{ik}\left(\tilde{\mathbf{a}}_{k}-\mathbf{b}_{k}^{a}-\boldsymbol{\eta}_{k}^{a}\right)\Delta
t^{2}\right]$

In this paper, we exploit these on-manifold integrated motion constraints as
efficient motion features for learning-based models. In other words, rather
than feeding a recurrent neural network (RNN) with the raw and high-frequency
IMU data, we use preintegration in order to reduce the temporal dimension of
the inputs, which is the root of the achieved efficiency. Moreover, the
reduced temporality and the induced geometrical bias in formulating this input
leads to improved predictive performance as shown in our experiments.

It is important to note that in this work, we disregard the biases in Eq. 2 by
assigning them with random values during the training as a data augmentation
technique.

###  2.2. The Baseline Model

####  2.2.1. The Network Architecture

Drawing inspiration from the double integration nature of the IMU kinematics
model, we have adopted a two-layer bidirectional LSTM architecture as our
baseline neural network. As illustrated in Fig. 1, this model is comprised of
two layers with 32 and 128 hidden units. The features extracted by the second
LSTM layer are then linearly mapped into 6-DOF $\mathfrak{se}(3)$ odometry
labels. These $\mathfrak{se}(3)$ vectors are the logarithmic maps of the
expected $SE(3)$ odometry transformations between poses $\boldsymbol{T}_{i-1}$
and $\boldsymbol{T}_{i}$:

(3)
$\displaystyle\boldsymbol{\xi}_{i}=\log{(\boldsymbol{T}_{i-1}^{-1}\boldsymbol{T}_{i})}^{\vee}\in\mathbb{R}^{6}$

Our motivation for bi-directionality is the ability of this model to attend to
both future and the past samples within a window of IMU measurements, and we
have chosen the larger 128-unit hidden size for the second layer to facilitate
better $\mathfrak{se}(3)$ regression. Overall, the baseline model has $210K$
parameters.

####  2.2.2. Loss Formulation

We adopt the formulation presented in (Peretroukhin and Kelly, 2018) and
formulate the training loss as the weighted sum of squares of the geodesic
distances between the ground truth odometry labels,
$\Delta\boldsymbol{T^{*}}_{i-1,i}=\boldsymbol{T^{*}}_{i-1}^{-1}\boldsymbol{T^{*}}_{i}$,
and the network’s outputs as follows:

(4) $\displaystyle L$
$\displaystyle=\sum_{k=1}^{N}\boldsymbol{g}_{i}^{T}\boldsymbol{\Sigma}^{-1}\boldsymbol{g}_{i}$
$\displaystyle\boldsymbol{g}_{i}$ $\displaystyle=log(\boldsymbol{\Delta
T^{*}}_{i,i+1}^{-1}\exp{(\boldsymbol{\xi}_{i}^{\wedge})})^{\vee}$

Where $(.)^{\wedge}$ and $(.)^{\vee}$ operators respectively transform the
$\mathfrak{se}(3)$ vectors into their skew symmetric matrix form and vise
versa. The $\boldsymbol{\Sigma}$ parameter in the above equation is an
empirical covariance matrix computed using the training data based on the
following equations:

(5) $\displaystyle\boldsymbol{\Sigma}$
$\displaystyle=\frac{1}{N-1}\sum_{i=1}^{N}\left(\boldsymbol{\xi}_{i}^{*}-\overline{\boldsymbol{\xi}^{*}}\right)\left(\boldsymbol{\xi}_{i}^{*}-\overline{\boldsymbol{\xi}^{*}}\right)^{T}$
$\displaystyle\overline{\boldsymbol{\xi}^{*}}$
$\displaystyle\triangleq\frac{1}{N}\sum_{i=1}^{N}\boldsymbol{\xi}_{i}^{*}$

where $N$ is the number of labels in the training dataset, and
$\boldsymbol{\xi}^{*}_{i}=\log{(\Delta\boldsymbol{T}_{i-1,i})}^{\vee}$. The
computed covariance in the above equation balances the relative importance of
each motion axis and stabilizes the training.

##  3\. Experiments and Studies

###  3.1. Datasets

We evaluate our approach on two different application domains: (1) autonomous
driving, and (2) pedestrian odometry. For _autonomous driving_ , the KITTI
odometry dataset (Geiger et al., 2012) has been chosen. This dataset is
recorded using a car equipped with vision, Lidar, and RTK-GPS+IMU units
traveling around urban and countryside environments. The IMU data is recorded
at a rate of 100 Hz, and the ground truth is provided at 10 Hz through a batch
maximum likelihood estimation based on Lidar and GPS data.

For the _pedestrian odometry_ application, the handheld and trolley domains of
the OxfordIO dataset (Chen et al., 2018b) have been chosen. OxfordIO dataset
contains the IMU readings from a smartphone held in various configurations and
carried by a user while undergoing different motion patterns. The ground truth
for this dataset is provided using a Vicon motion capture system with
millimeter-level accuracy.

###  3.2. Baseline Implementation

We implemented our model using PyTorch and PytorchLightning frameworks and ran
the training process on an Nvidia T4 GPU. Adam optimizer with a learning rate
of $0.001$ is used to train the models. On average, the convergence happened
after 120 epochs. To avoid overfitting, dropout layers have been used after
each LSTM layer to zero out $25\%$ of the neuron activities at each iteration.
Our implementations will be open sourced333https://github.com/Rooholla-
KhorramBakht/pi_net.

###  3.3. Baseline Results

####  3.3.1. Autonomous Driving

In this section we train three models. As the base of comparison, we train our
baseline model using raw IMU data over 1280 IMU samples which corresponds to
12.8 seconds of IMU measurements. Furthermore, to compare preintegration with
a naive Euclidean averaging, we averaged each 10 IMU sample into one
measurement and trained a model with 128 such measurements. Finally, our main
experiment trains the baseline model on preintegrated features each computed
over 10 IMU samples, which leads to 128 input features. Our motivation for
choosing an integration factor of 10 has been the 10 Hz ground-truth frequency
of the KTIIT dataset as opposed to the 100 Hz IMU samples.

The test/train splitting policy for the KITTI dataset follows the common
practice in data-driven VIO literature (Chen et al., 2019b), which takes
sequences 05, 07, and 10 for testing, and sequences {00-10}-{05,07,10,03} for
training. We report our results as relative translation and rotation errors
defined by the KITTI benchmark (Geiger et al., 2012). These relative errors
are defined as the averaged position/orientation errors within all possible
sub-sequences of lengths $100m,...,800m$.

Table 1. Relative odometry translation ($\%$) and orientation ($deg/100m$) errors on the KITTI dataset. test seq. |  | Raw IMU
---
| Averaged IMU
---
|  PI-Features (ours)
---
| $t_{rel}$
---
| $r_{rel}$
---
| $t_{rel}$
---
| $r_{rel}$
---
| $t_{rel}$
---
| $r_{rel}$
---
05 | 10.95 | 2.06 | 17.02 | 2.73 | 4.75 | 0.85
07 | 16.07 | 4.42 | 14.04 | 2.04 | 9.06 | 1.56
10 | 7.57 | 1.52 | 9.03 | 2.41 | 5.26 | 0.75
avg. | 11.53 | 2.66 | 13.36 | 2.38 | 6.35 | 1.05

Table 1 represents the overall comparison between the results of our three
experiments. As it can be seen from the first and second columns of the table,
the average translation and orientation errors of averaged measurements is the
lowest and as shown in the third column, the baseline model trained using the
preintegrated features consistently achieves the best results compared to both
averaged and raw inputs. This performance improvement is also qualitatively
evident from Fig. 2. As shown in this figure, the models trained using the
preintegrated IMU features exhibit better orientation stability which in turn
leads to better translational accuracy.

(a) Seq. 05

(b) Seq. 07

(c) Seq. 10

Figure 2. Qualitative comparison between the baseline model with raw, averaged, and preintegrated IMU inputs on KITTI datasets. This figure is best viewed in the color version. Table 2. Relative translation errors on OxfordIO dataset (handheld/trolley-data _#_ -sequence _#_) Method | h-d1-s2 | h-d1-s5 | h-d1-s6 | h-d3-s1 | h-d4-s1 | h-d4-s3 | h-d5-s1 | t_d2_s6 | average
---|---|---|---|---|---|---|---|---|---
PI Features (Ours) ($\%$) | $\mathbf{5.52}$ | $\mathbf{2.66}$ | $\mathbf{2.98}$ | $\mathbf{3.64}$ | $\mathbf{4.16}$ | $\mathbf{3.27}$ | $\mathbf{3.3}$ | $7.61$ | $\mathbf{4.14}$
Raw IMU ($\%$) | $6.5$ | $3.33$ | $3.12$ | $4.45$ | $4.32$ | $4.6$ | $3.64$ | $\mathbf{4.87}$ | $4.35$

We believe that the geometrical inductive bias in calculating the
preintegrated features and the reduced burden of memorizing long sequences of
raw measurements contribute to this performance improvement when using
preintegrated features. Furthermore, as shown in the second column of the
table, a naive averaging of the IMU measurements leads to information loss and
loss of performance compared to a model trained using raw IMU inputs.

####  3.3.2. Pedestrian Odometry

We also investigate the effectiveness of our approach for the domain of
pedestrian odometry using the OxfordIO dataset. Since naive averaging was
shown to be ineffective for deep inertial odometry in the previous section,
this section considers only the model trained using the raw IMU inputs as the
baseline.

As a metric, we integrate the 6-DoF odometry outputs from both models for
batches of 200 IMU measurements, which translates to 2 seconds of walking. The
two predictions are then compared against the ground truth to compute the
error for each model. We then divide these errors by the displacement length
to normalize them.

The experiments in the OxfordIO dataset have been carried out for the trolley
and handheld motion domains. The relative translation errors are described in
Table 2. As it can be seen from comparing errors in the first and second row
of Table 2, a model trained with preintegrated IMU features as input
consistently surpasses the baseline trained using the raw IMU measurements.

The only exception is for the trolley domain. Our intuition is that the model
trained using the raw data on the trolley domain enjoys the unattenuated high-
frequency contents induced by the vibrations of the wheel. This spectral
modality helps the model to distinguish various motion states of the trolley
and is filtered out by the low pass nature of the integration in the
computation of the preintegrated features. As a future research direction, we
aim to investigate the extension of preintegrated features with spectral
information.

###  3.4. Embedded Implementation

The baseline architectures in the previous subsection were executed on an
NVIDIA GTX1050 GPU and required $1ms$ to process $20\times 9$ PI features and
$3.7ms$ for its corresponding $200\times 6$ raw IMU samples (two seconds of
data in our datasets). This substantial performance improvement is due to the
compressed temporal dimension of the IMU thus fewer LSTM recursions. In this
section, we aim to show that IMU preintegration can enable deep inertial
odometry even for highly constrained platforms such as microcontrollers. To
this aim, we reproduce the IO-Net formulation of deep inertial odometry (Chen
et al., 2020). Specifically, we train a small Convolutional Neural Network
(CNN) that takes a 2D $9\times T$ feature map created by stacking $T$
preintegrated IMU features as input and predicts the corresponding translation
and heading change in polar coordinate. For comparison purposes, we also
construct a bi-LSTM model with the same output format. Two versions of this
baseline are then trained using the preintegrated features and raw IMU
measurements as inputs.

####  3.4.1. Architecture

The architecture of the LSTM baseline is similar to the model shown in Fig. 1.
The only difference is that the predictions are taken from the feature map of
the last timestamp, and the number of hidden units are chosen to be 128 and
256 for the first and second layers to match the values reported in (Chen et
al., 2020). The feature map corresponding to the last timestamp is then
linearly mapped to a $\Delta\Phi$ and $\Delta L$ polar odometry prediction.
Similar to the design choice of the IO-Net implementation, we break the raw
IMU data into separate windows of 200 samples (2 seconds) and process each of
them individually to yield the odometry output $(\Delta L,\Delta\Phi)$ in
polar coordinates. Each odometry output updates the subject’s position based
on the following kinematic model:

(6) $\begin{cases}\Phi_{n+1}&=\Phi_{n-1}+\Delta\Phi\\\ X_{n}&=X_{n-1}+\Delta
Lcos(\Phi_{n})\\\ Y_{n}&=Y_{n-1}+\Delta Lsin(\Phi_{n})\end{cases}$

Based on the above equation, the old heading $\Phi_{n}$ is updated using the
$\Delta\Phi$ odometry output. The updated $\Phi_{n+1}$ is then used alongside
the odometry output $\Delta L$ to update the position
$P_{n}=[X_{n},Y_{n}]^{T}$.

A smaller feedforward CNN model has been chosen for the microcontroller
implementation. As shown in Fig. 3, this model takes the stacked PI features
as input and passes them through two CNN layers, one with a kernel size of
$3\times 3\times 16$ and the other with a kernel size of $1\times 1\times 4$.
The extracted feature is eventually mapped into two scalar outputs
corresponding to the $\Delta\Phi$ and $\Delta L$ polar odometry predictions.

It is important to note that the temporally compressed preintegrated features
enable shallow CNNs to cover a much larger temporal receptive field of the
motion signal. As a result, one may drastically shrink the model dimension and
kernel sizes which facilitate the embedded implementation of the model.

Figure 3.  The proposed CNN model for the embedded implementation of the IO-
Net pedestrian odometry. In the figure, $n$ is the integration length and in
this paper is set to 10.

####  3.4.2. Training and Metrics

We train the model using the mean squared difference between the expected and
predicted polar values which is formulated as follows:

(7) $L=\sum_{i=1}^{N}||\Delta
L_{i}-\Delta\hat{L}_{i}||_{2}^{2}+\beta||\Delta\Phi_{i}-\Delta\hat{\Phi}_{i}||_{2}^{2}$

where $N$ is the number of training sequences in the batch, $\Delta
L_{i},\Delta Phi_{i}$ are the network’s outputs, and
$\Delta\hat{L_{i}},\Delta\hat{\Phi_{i}}$ are the ground-truth labels.
Furthermore, the $\beta$ hyperparameter in the above equation provides a
balance between the orientation and translation components of the loss. This
paper sets this parameter based on the average norm of the orientation and
translation losses on a randomly initialized model such that the two terms
would contribute equally in the backpropagation.

$\Delta\hat{\Phi_{i}}$ heading label is the projection of the orientation
difference between the first and the last sample in the window, and is
calculated as follows:

(8)
$\Delta\hat{\Phi_{i}}=log(\boldsymbol{R_{i}}^{T}\boldsymbol{R_{i+199}})^{\vee}$

where $\log(.)$ function in the above equation is the $SO3$ logarithmic map
and $R_{i}$ represents the ground-truth label for the $i^{th}$ sample.
Furthermore, $\Delta\hat{L_{i}}$ is calculated as the Euclidean distance
between the x-y projections of the first and the last position within a
window:

(9) $\Delta\hat{L_{i}}=\sqrt{(X_{i}-X_{i+199})^{2}+(Y_{i}-Y_{i+199})^{2}}$

The Root Mean Square Error (RMSE) metric has also been adopted for comparing
the results quantitatively. Instead of comparing the integrated paths, we opt
to compare the odometry outputs since it provides a more direct comparison.

####  3.4.3. Performance of The Trained Models

Table 3. RMS error of CNN and baseline IO-Net models trained using preintegrated and raw IMU measurements. |  | Base Model
---
$(\Delta L(m/S),\Delta\Phi(rad/S))$
| Model with Preintegrated Input
---
$(\Delta L(m/S),\Delta\Phi(rad/S))$
| Embedded CNN Model
---
$(\Delta L(m/S),\Delta\Phi(rad/S))$
Slow Walking | $(0.18,0.013)$ | $(\mathbf{0.017,0.013})$ | $(0.029,0.013)$
Running | $({0.125},{0.255})$ | $\mathbf{(0.1,0.216)}$ | $(0.115,0.26)$
Pocket | $(0.0141,0.025)$ | $\mathbf{(0.014,0.025)}$ | $(0.021,0.027)$
Handbag | $(0.041,0.0261)$ | $(\mathbf{0.032},\mathbf{0.081})$ | $(0.048,0.081)$

Table 3 presents the model’s performances on slow walking, running, phone in
pocket, and phone in the handbag domains. The reported numbers are the average
rate of change for the heading and stride predictions, $(\Delta L/\Delta
T,\Delta\Phi/\Delta T)$. The first and the second columns present the baseline
LSTM model trained using the raw inputs, and the second column represents the
result trained using the preintegrated features.

Furthermore, The third column presents the performance of the small CNN model.
As verified in the previous sections, with preintegration, the heading and
stride predictive performance is improved compared to the model trained with
raw inputs. On the other hand, we can see that the CNN model performs
reasonably well even though its complexity is highly reduced compared to the
stacked LSTM baseline. Despite this simplicity, it is interesting to note that
the CNN model trained on preintegrated inputs performs on par with the
baseline IO-Net trained using raw measurements.

####  3.4.4. Implementation

The embedded implementation of the CNN model is carried out using the X-Cube-
AI framework (STM, 2020), and the preintegration processing has been
implemented using the highly optimized ARM CMSIS-DSP math library. While we
could have quantized the Keras model for improving its performance, we used
the floating-point version due to its generality and faster implementation. On
the lowest level of the X-Cube-AI framework, a run-time utilizes the ARM
CMSIS-NN/DSP libraries (ARM, 2020) to run the converted Keras network
efficiently. The user application may then load the run-time with the
appropriate network for inference. In this paper, the target platform is an
ARM STM32F407ZET microcontroller with 198KB of RAM and 512KB of flash memory,
and with a Cortex-M4 CPU running at 168Mhz.

Table 4. Resource consumption and performance on an _STM32F407ZET_ microcontroller with $512KBi$ of Flash and $192KBi$ of RAM running at a clock frequency of $168MHz$. Process | RAM Usage (KB) | ROM Usage (KB) | Execution Time (ms)
---|---|---|---
Preintegration (per vector) | 4 (Stack Size) | 0 (No Parameters) | 0.2
Model Inference | 12.28 | 92.55 | 5

Table 4 presents the implementational details of the CNN model on this
microcontroller. As seen in the table, calculating each preintegration vector
takes about 0.2ms while each model inference requires only 5ms of
computational time. Assuming a stride of 10 (running the inference after each
10 IMU measurements), each inference requires calculating one preintegrated
feature and running one model inference, which in total takes 5.2ms. Since
this computation is required every 100 milliseconds, there will be plenty of
CPU time left for other user-specific tasks.

Furthermore, the model’s memory consumption is reasonably low and is around
$92.55/512KB$ for flash and $12.28/192KB$ for RAM which leaves plenty of room
for other user-specific data and code. Furthermore, the successful processing
of the preintegration vectors in the microcontroller required increasing the
stack to 4KB which is reported here as the approximate required RAM for
performing preintegration.

##  4\. Conclusions and Future Works

This paper proposed a computationally efficient preprocessing method for raw
IMU measurements that utilizes the manifold structure of the IMU model to
compress long sequences of raw measurements into short and effective motion
representations for deep inertial odometry. This compression improves the
computational efficiency of deep motion estimation in embedded applications.
In addition to this added efficiency, this paper showed improved odometry
performance based on preintegrated features through experiments carried out in
two distinct domains of pedestrian inertial odometry and autonomous vehicles.
Finally, the efficiency of our approach was demonstrated through the
formulation of a well-known pedestrian odometry model based on preintegrated
features and its implementation on an embedded microcontroller with highly-
restricted resources. Prominent directions for future research are applying
preintegration for other applications such as human activity recognition and
visual-inertial odometry. Furthermore, the proposed PI feature may be enriched
using acoustic features such as FFTs to encode the vibration modality
alongside the preintegrated motion vectors, which may provide further
improvements in terms of accuracy and robustness.

## References

  * (1)
  * STM (2020) 2020\.  _Getting started with X-CUBE-AI Expansion Package for Artificial Intelligence (AI) UM2526 User manual_.  Technical Report.
  * Almalioglu et al. (2019) Yasin Almalioglu, Mehmet Turan, Alp Eren Sari, Muhamad Risqi U. Saputra, Pedro P. B. de Gusmão, Andrew Markham, and Niki Trigoni. 2019\.  SelfVIO: Self-Supervised Deep Monocular Visual-Inertial Odometry and Depth Estimation.  (2019).  arXiv:1911.09968 http://arxiv.org/abs/1911.09968
  * ARM (2020) ARM. 2020.  CMSIS DSP Software Library.  http://www.keil.com/pack/doc/CMSIS/DSP/html/index.html
  * Brossard et al. (2019) Martin Brossard, Axel Barrau, and Silvere Bonnabel. 2019\.  RINS-W: Robust Inertial Navigation System on Wheels.  _IEEE International Conference on Intelligent Robots and Systems_ (2019).  https://doi.org/10.1109/IROS40897.2019.8968593 arXiv:1903.02210
  * Chen et al. (2018a) Changhao Chen, Xiaoxuan Lu, Andrew Markham, and Niki Trigoni. 2018a.  IoNet: Learning to cure the curse of drift in inertial odometry.  _32nd AAAI Conference on Artificial Intelligence, AAAI 2018_ (2018).  arXiv:1802.02209
  * Chen et al. (2019a) Changhao Chen, Xiaoxuan Lu, Johan Wahlstrom, Andrew Markham, and Niki Trigoni. 2019a.  Deep neural network based inertial odometry using low-cost inertial measurement units.  _IEEE Transactions on Mobile Computing_ (2019).
  * Chen et al. (2019b) Changhao Chen, Stefano Rosa, Yishu Miao, Chris Lu, Wei Wu, Andrew Markham, and Niki Trigoni. 2019b.  Selective Sensor Fusion for Neural Visual-Inertial Odometry. 10534–10543.  https://doi.org/10.1109/CVPR.2019.01079
  * Chen et al. (2018b) Changhao Chen, P. Zhao, Chris Xiaoxuan Lu, W. Wang, A. Markham, and A. Trigoni. 2018b.  OxIOD: The Dataset for Deep Inertial Odometry.  _ArXiv_ abs/1809.07491 (2018).
  * Chen et al. (2020) Changhao Chen, Peijun Zhao, Chris Xiaoxuan Lu, Wei Wang, Andrew Markham, and Niki Trigoni. 2020\.  Deep-Learning-Based Pedestrian Inertial Navigation: Methods, Data Set, and On-Device Inference.  _IEEE Internet of Things Journal_ 7, 5 (2020), 4431–4441.  https://doi.org/10.1109/JIOT.2020.2966773 arXiv:2001.04061
  * Damirchi et al. (2020) Hamed Damirchi, Rooholla Khorrambakht, and Hamid Taghirad. 2020\.  ARC-Net: Activity Recognition Through Capsules.  _arXiv preprint arXiv:2007.03063_ (2020).
  * Dellaert (2021) Frank Dellaert. 2021\.  Factor graphs: Exploiting structure in robotics.  _Annual Review of Control, Robotics, and Autonomous Systems_ 4 (2021), 141–166.
  * Forster et al. (2017) Christian Forster, Luca Carlone, Frank Dellaert, and Davide Scaramuzza. 2017.  On-Manifold Preintegration for Real-Time Visual-Inertial Odometry.  _IEEE Transactions on Robotics_ 33, 1 (2017).  https://doi.org/10.1109/TRO.2016.2597321
  * Geiger et al. (2012) Andreas Geiger, Philip Lenz, and Raquel Urtasun. 2012\.  Are we ready for Autonomous Driving? The KITTI Vision Benchmark Suite. In _Conference on Computer Vision and Pattern Recognition (CVPR)_.
  * Huang (2019) Guoquan Huang. 2019\.  Visual-inertial navigation: A concise review.  _Proceedings - IEEE International Conference on Robotics and Automation_ 2019-May (2019).  https://doi.org/10.1109/ICRA.2019.8793604 arXiv:1906.02650
  * Peretroukhin and Kelly (2018) V. Peretroukhin and J. Kelly. 2018.  DPC-Net: Deep Pose Correction for Visual Localization.  _IEEE Robotics and Automation Letters_ 3, 3 (2018), 2424–2431.  https://doi.org/10.1109/LRA.2017.2778765
  * Sandy et al. (2019) Timothy Sandy, Lukas Stadelmann, Simon Kerscher, and Jonas Buchli. 2019.  ConFusion: Sensor Fusion for Complex Robotic Systems using Nonlinear Optimization.  _IEEE Robotics and Automation Letters_ PP, c (2019).  https://doi.org/10.1109/LRA.2019.2894168 arXiv:1806.07115
  * Saputra et al. (2020) Muhamad Risqi U. Saputra, Niki Trigoni, Pedro P.B. De Gusmao, Chris Xiaoxuan Lu, Yasin Almalioglu, Stefano Rosa, Changhao Chen, Johan Wahlstrom, Wei Wang, and Andrew Markham. 2020.  DeepTIO: A deep thermal-inertial odometry with visual hallucination.  _IEEE Robotics and Automation Letters_ 5, 2 (2020).  https://doi.org/10.1109/LRA.2020.2969170 arXiv:1909.07231
  * Wagstaff et al. (2020) Brandon Wagstaff, Valentin Peretroukhin, and Jonathan Kelly. 2020\.  Robust Data-Driven Zero-Velocity Detection for Foot-Mounted Inertial Navigation.  _IEEE Sensors Journal_ 20, 2 (2020).  https://doi.org/10.1109/JSEN.2019.2944412 arXiv:1910.00529


11institutetext:  †University of Chinese Academy of Sciences
National Laboratory of Pattern Recognition, CASIA
‡CAS Center for Excellence in Brain Science and Intelligence Technology
<EMAIL_ADDRESS>

# Look-ahead Attention for Generation in Neural Machine Translation

Long Zhou† Jiajun Zhang† Chengqing Zong†‡

###### Abstract

The attention model has become a standard component in neural machine
translation (NMT) and it guides translation process by selectively focusing on
parts of the source sentence when predicting each target word. However, we
find that the generation of a target word does not only depend on the source
sentence, but also rely heavily on the previous generated target words,
especially the distant words which are difficult to model by using recurrent
neural networks. To solve this problem, we propose in this paper a novel look-
ahead attention mechanism for generation in NMT, which aims at directly
capturing the dependency relationship between target words. We further design
three patterns to integrate our look-ahead attention into the conventional
attention model. Experiments on NIST Chinese-to-English and WMT English-to-
German translation tasks show that our proposed look-ahead attention mechanism
achieves substantial improvements over state-of-the-art baselines.

##  1 Introduction

Neural machine translation (NMT) has significantly improved the quality of
machine translation in recent several years [10, 26, 1, 9], in which the
attention model increasingly plays an important role. Unlike traditional
statistical machine translation (SMT) [13, 4, 32] which contains multiple
separately tuned components, NMT builds upon a single and large neural network
to directly map source sentence to associated target sentence.

Typically, NMT adopts the encoder-decoder architecture which consists of two
recurrent neural networks. The encoder network models the semantics of the
source sentence and transforms the source sentence into context vector
representation, from which the decoder network generates the target
translation word by word. Attention mechanism has become an indispensable
component in NMT, which enables the model to dynamically compose source
representation for each timestep during decoding, instead of a single and
static representation. Specifically, the attention model shows which source
words the model should focus on in order to predict the next target word.

However, previous attention models are mainly designed to predict the
alignment of a target word with respect to source words, which take no account
of the fact that the generation of a target word may have a stronger
correlation with the previous generated target words. Recurrent neural
networks, such as gated recurrent units (GRU) [5] and long short term memory
(LSTM) [8], still suffer from long-distance dependency problems, according to
pioneering studies [1, 12] that the performance of NMT is getting worse as
source sentences get longer. Figure 1 illustrates an example of Chinese-
English translation. The dependency relationship of target sentence determines
whether the predicate of the sentence should be singular (is) or plural (are).
While the conventional attention model does not have a specific mechanism to
learn the dependency relationship between target words.

To address this problem, we propose in this paper a novel look-ahead attention
mechanism for generation in NMT, which can directly model the long-distance
dependency relationship between target words. The look-ahead attention model
does not only align to source words, but also refer to the previous generated
target words when generating a target word. Furthermore, we present and
investigate three patterns for the look-ahead attention, which can be
integrated into any attention-based NMT. To show the effectiveness of our
look-ahead attention, we have conducted experiments on NIST Chinese-to-English
translation tasks and WMT14 English-to-German translation tasks. Experiments
show that our proposed model obtains significant BLEU score improvements over
strong SMT baselines and a state-of-the-art NMT baseline.

Figure 1: An example of Chinese-English translation. The English sentence is
analyzed using Stanford online
parser111http://nlp.stanford.edu:8080/parser/index.jsp.. Although the
predicate “ _are pushing_ ” is close to the word “ _France_ ”, it has a
stronger dependency on the word “ _countries_ ” instead of “ _France_ ”.

##  2 Neural Machine Translation

Our framework integrating the look-ahead attention mechanism into NMT can be
applied in any conventional attention model. Without loss of generality, we
use the improved attention-based NMT proposed by Luong et al. [16], which
utilizes stacked LSTM layers for both encoder and decoder as illustrated in
Figure 2.

The NMT first encodes the source sentence $X=(x_{1},x_{2},...,x_{m})$ into a
sequence of context vector representation $C=(h_{1},h_{2},...,h_{m})$ whose
size varies with respect to the source sentence length. Then, the NMT decodes
from the context vector representation $C$ and generates target translation
$Y=(y_{1},y_{2},...,y_{n})$ one word each time by maximizing the probability
of $p(y_{j}|y_{<j},C)$. Next, we briefly review the encoder introducing how to
obtain $C$ and the decoder addressing how to calculate $p(y_{j}|y_{<j},C)$.

Figure 2: The architecture of neural machine translation model.

Encoder: The context vector representation
$C=(h_{1}^{l},h_{2}^{l},...,h_{m}^{l})$ are generated by the encoder using $l$
stacked LSTM layers. Bi-directional connections are used for the bottom
encoder layer, and $h_{i}^{1}$ is a concatenation of a left-to-right
$\overrightarrow{h}_{i}^{1}$ and a right-to-left$\overleftarrow{h}_{i}^{1}$,

$h_{i}^{1}=\begin{bmatrix}\overrightarrow{h}_{i}^{1}\\\
\overleftarrow{h}_{i}^{1}\end{bmatrix}=\begin{bmatrix}LSTM(\overrightarrow{h}_{i-1}^{1},x_{i})\\\
LSTM(\overleftarrow{h}_{i-1}^{1},x_{i})\end{bmatrix}$ (1)

All other encoder layers are unidirectional, and $h_{i}^{k}$ is calculated as
follows:

$h_{i}^{k}=LSTM(h_{i-1}^{k},h_{i}^{k-1})$ (2)

Decoder: The conditional probability $p(y_{j}|y_{<j},C)$ is formulated as

$p(y_{j}|Y_{<j},C)=p(y_{j}|Y_{<j},c_{j})=softmax(W_{s}t_{j})$ (3)

Specifically, we employ a simple concatenation layer to produce an attentional
hidden state $t_{j}$:

$t_{j}=tanh(W_{c}[s_{j}^{l};c_{j}]+b)=tanh(W_{c}^{1}s_{j}^{l}+W_{c}^{2}c_{j}+b)$
(4)

where $s_{j}^{l}$ denotes the target hidden state at the top layer of a
stacking LSTM. The attention model calculates $c_{j}$ as the weighted sum of
the source-side context vector representation, just as illustrated in the
upper left corner of Figure 2.

$c_{j}=\sum_{i=1}^{m}ATT(s_{j}^{l},h_{i}^{l})\cdot
h_{i}^{l}=\sum_{i=1}^{m}\alpha_{ji}h_{i}^{l}$ (5)

where $\alpha_{ji}$ is a normalized item calculated as follows:

$\alpha_{ji}=\frac{exp(h_{i}^{l}\cdot
s_{j}^{l})}{\sum_{i^{{}^{\prime}}}exp(h_{i^{{}^{\prime}}}^{l}\cdot
s_{j}^{l})}$ (6)

$s_{j}^{k}$ is computed by using the following formula:

$s_{j}^{k}=LSTM(s_{j-1}^{k},s_{j}^{k-1})$ (7)

If $k=1$, $s_{j}^{1}$ will be calculated by combining $t_{j-1}$ as feed input
[16]:

$s_{j}^{1}=LSTM(s_{j-1}^{1},y_{j-1},t_{j-1})$ (8)

Given the bilingual training data $D=\\{(X^{(z)},Y^{(z)})\\}_{z=1}^{Z}$, all
parameters of the attention-based NMT are optimized to maximize the following
conditional log-likelihood:

$L(\theta)=\frac{1}{Z}\sum_{z=1}^{Z}\sum_{j=1}^{n}logp(y_{j}^{(z)}|y_{<j}^{(z)},X^{(z)},\theta)$
(9)

##  3 Model Description

Learning long-distance dependencies is a key challenge in machine translation.
Although the attention model introduced above has shown its effectiveness in
NMT, it takes no account of the dependency relationship between target words.
Hence, in order to relieve the burden of LSTM or GRU to carry on the target-
side long-distance dependencies, we design a novel look-ahead attention
mechanism, which directly establishes a connection between the current target
word and the previous generated target words. In this section, we will
elaborate on three proposed approaches about integrating the look-ahead
attention into the generation of attention-based NMT.

###  3.1 Concatenation Pattern

Figure 3(b) illustrates concatenation pattern of the look-ahead attention
mechanism. We not only compute the attention between current target hidden
state and source hidden states, but also calculate the attention between
current target hidden state and previous target hidden states. The look-ahead
attention output at timestep $j$ is computed as:

$c_{j}^{d}=\sum_{i=1}^{j-1}ATT(s_{j}^{l},s_{i}^{l})\cdot s_{i}^{l}$ (10)

where $ATT(s_{j}^{l},s_{i}^{l})$ is a normalized item.

Specifically, given the target hidden state $s_{j}^{l}$, the source-side
context vector representation $c_{j}$, and the target-side context vector
representation $c_{j}^{d}$, we employ a concatenation layer to combine the
information to produce an attentional hidden state as follows:

$t_{j}^{final}=tanh(W_{c}[s_{j}^{l};c_{j};c_{j}^{d}]+b)$ (11)

After getting the attentional hidden state $t_{j}^{final}$, we can calculate
the conditional probability $p(y_{j}|y_{<j},C)$ as formulated in Eq. 3.

Figure 3: Different architectures of look-ahead attention. (a) is the
conventional attention pattern as introduced in Eq. 4 of section 2. (b), (c)
and (d) are our three approaches which integrate look-ahead attention
mechanism into attention-based NMT.

###  3.2 Enc-Dec Pattern

Concatenation pattern is a simple method to achieve look-ahead attention,
which regards source-side context vector representation and target-side
context vector representation as the same importance. Different from
concatenation pattern, Enc-Dec pattern utilizes a hierarchical architecture to
integrate look-ahead attention as shown in Figure 3(c).

Once we get the attentional hidden state of conventional attention-based NMT,
we can employ look-ahead attention mechanism to update the previous
attentional hidden state. In detail, the model first computes the attentional
hidden state $t_{j}^{e}$ of conventional attention-based NMT as Eq. 4. Second,
the model calculates the attention between the attentional hidden state
$t_{j}^{e}$ and previous target hidden states:

$c_{j}^{d}=\sum_{i=1}^{j-1}ATT(t_{j}^{e},s_{i}^{l})\cdot s_{i}^{l}$ (12)

Then, the final attentional hidden state is calculated as followed:

$t_{j}^{final}=tanh(W_{c2}[t_{j}^{e};c_{j}^{d}]+b_{2})$ (13)

###  3.3 Dec-Enc Pattern

Dec-Enc pattern is the opposite of the Enc-Dec pattern, and it uses look-ahead
attention mechanism to help the model align to source words. Figure 3(d) shows
this pattern. We compute look-ahead attention output firstly as Eq. 10, and
attentional hidden state is computed by:

$t_{j}^{d}=tanh(W_{c1}[s_{j}^{l};c_{j}^{d}]+b)$ (14)

Finally, we can calculate the attention between the attentional hidden state
$t_{j}^{d}$ and source hidden states to get final attentional hidden state:

$t_{j}^{final}=tanh(W_{c2}[t_{j}^{d};c_{j}^{e}]+b_{2})$ (15)
$c_{j}^{e}=\sum_{i=1}^{m}ATT(t_{j}^{d},h_{i}^{l})\cdot h_{i}^{l}$ (16)

where $h_{i}^{l}$ is source-side hidden state at the top layer.

##  4 Experiments

###  4.1 Dataset

We perform our experiments on the NIST Chinese-English translation tasks and
WMT14 English-German translation tasks. The evaluation metric is BLEU [21] as
calculated by the multi-blue.perl script.

For Chinese-English, our training data consists of 630K sentence pairs
extracted from LDC corpus222The corpora include LDC2000T50, LDC2002T01,
LDC2002E18, LDC2003E07, LDC2003E14, LDC2003T17 and LDC2004T07.. We use NIST
2003(MT03) Chinese-English dataset as the validation set, NIST 2004(MT04),
NIST 2005(MT05), NIST 2006(MT06) datasets as our test sets. Besides, 10M
Xinhua portion of Gigaword corpus is used in training language model for SMT.

For English-German, to compare with the results reported by previous work [16,
25, 34], we used the same subset of the WMT 2014 training
corpus333http://www.statmt.org/wmt14/translation-task.html that contains 4.5M
sentence pairs with 116M English words and 110M German words. The
concatenation of news-test 2012 and news-test 2013 is used as the validation
set and news-test 2014 as the test set.

###  4.2 Training Details

We build the described models modified from the
Zoph_RNN444https://github.com/isi-nlp/Zoph_RNN toolkit which is written in
C++/CUDA and provides efficient training across multiple GPUs. Our training
procedure and hyper parameter choices are similar to those used by Luong et
al. [16]. In the NMT architecture as illustrated in Figure 2, the encoder has
three stacked LSTM layers including a bidirectional layer, followed by a
global attention layer, and the decoder contains two stacked LSTM layers
followed by the softmax layer.

In more details, we limit the source and target vocabularies to the most
frequent 30K words for Chinese-English and 50K words for English-German. The
word embedding dimension and the size of hidden layers are all set to 1000.
Parameter optimization is performed using stochastic gradient descent(SGD),
and we set learning rate to 0.1 at the beginning and halve the threshold while
the perplexity go up on the development set. Each SGD is a mini-batch of 128
examples. Dropout was also applied on each layer to avoid over-fitting, and
the dropout rate is set to 0.2. At test time, we employ beam search with beam
size b = 12.

###  4.3 Results on Chinese-English Translation

We list the BLEU scores of our proposed model in Table 1. Moses-1 [11] is the
state-of-the-art phrase-based SMT system with the default configuration and a
4-gram language model trained on the target portion of training data. Moses-2
is the same as Moses-1 except that the language model is trained using the
target data plus 10M Xinhua portion of Gigaword corpus. The BLEU score of our
NMT baseline, which is an attention-based NMT as introduced in Section 2, is
about 4.5 higher than the state-of-the-art SMT system Moses-2.

Table 1: Translation results (BLEU score) for Chinese-to-English translation. “$\dagger$”: significantly better than NMT Baseline ($p<0.05$). “$\ddagger$”: significantly better than NMT Baseline ($p<0.01$). System |  MT04 |  MT05 |  MT06 |  Ave
---|---|---|---|---
Moses-1 |  31.08 |  28.37 |  30.04 |  29.83
Moses-2 |  33.13 |  31.38 |  32.63 |  32.38
NMT Baseline |  38.96 |  34.95 |  36.65 |  36.85
Concatenation pattern |  39.43$\dagger$ |  35.40$\dagger$ |  36.93 |  37.25$\dagger$
Enc-Dec pattern |  39.61$\dagger$ |  36.50$\ddagger$ |  37.23$\dagger$ |  37.78$\ddagger$
Dec-Enc pattern |  39.00 |  36.36$\ddagger$ |  37.01$\dagger$ |  37.46$\ddagger$

For the last three lines in Table 1, Enc-Dec pattern outperforms concatenation
pattern and even Dec-Enc pattern, which shows Enc-Dec pattern is best approach
to take advantage of look-ahead attention. Moreover, our Enc-Dec pattern gets
an improvement of +0.93 BLEU points over the state-of-the-art NMT baseline,
which demonstrates that the look-ahead attention mechanism is effective for
generation in conventional attention-based NMT.

####  4.3.1 Effects of Translating Long Sentences

A well-known flaw of NMT model is the inability to properly translate long
sentences. One of the goals that we integrate the look-ahead attention into
the generation of NMT decoder is boosting the performance in translating long
sentence. We follow Bahdanau et al. [1] to group sentences of similar lengths
together and compute a BLEU score per group, as demonstrated in Figure 4.

Figure 4: Length Analysis \- translation qualities(BLEU score) of our proposed
model and the NMT baseline as sentences become longer.

Although the performance of both the NMT baseline and our proposed model drops
rapidly when the length of source sentence increases, our Enc-Dec model is
more effective than the NMT Baseline in handling long sentences. Specifically,
our proposed model gets an improvement of 1.88 BLEU points over the baseline
from 50 to 60 words in source language. Furthermore, when the length of input
sentence is greater than 60, our model still outperforms the baseline by 1.04
BLEU points. Experiments show that the look-ahead attention can relieve the
burden of LSTM to carry on the target-side long-distance dependencies.

####  4.3.2 Target Alignment of Look-ahead Attention

The conventional attention models always refer to some source words when
generating a target word. We propose a look-ahead attention for generation in
NMT, which also focuses on previous generated words in order to predict the
next target word.

Figure 5: Target Alignment of Look-ahead Attention.

We provide two real translation examples to show the target alignment of look-
ahead attention in Figure 5. The first line is blank because it does not have
look-ahead attention when generating the first word. Every line represents the
weight distribution for previous generated words when predicting current
target word. More specifically, we find some interesting phenomena. First,
target words often refer to verb or predicate which has been generated
previously, such as the word “was” in Figure 5(a).

Second, the heat map shows that the word “we” and the word “looking” have a
stronger correlation when translating the Chinese sentence as demonstrated in
Figure 5(b). Intuitively, the look-ahead attention mechanism establishes a
bridge to capture the dependency relationship between target words. Third,
most target words mainly focus on the word immediately before the current
target word, which may be due to the fact that the last generated word
contains more information in recurrent neural networks. We can control the
influence of the look-ahead attention like Tu et al. [27] to improve
translation quality and instead we remain it as our future work.

###  4.4 Results on English-German Translation

We evaluate our model on the WMT14 translation tasks for English to German,
whose results are presented in Table 2. We find that our proposed look-ahead
attention NMT model also obtains significant accuracy improvements on large-
scale English-German translation.

Table 2: Translation results (BLEU score) for English-to-German translation. “$\ddagger$”: significantly better than Baseline($p<0.01$). System |  Architecture |  Voc. |  BLEU
---|---|---|---
Existing systems
Loung et al. [16] |  LSTM with 4 layers+dropout+local att. |  50K |  19.00
Shen et al. [25] |  Gated RNN with search + MRT |  50K |  18.02
Zhou et al. [34] |  LSTM with 16 layers + F-F connections |  160K |  20.60
Our NMT systems
This work |  Baseline |  50K |  19.84
This work |  Enc-Dec pattern |  50K |  20.36$\ddagger$

In addition, we compare our NMT systems with various other systems including
Zhou et al. [34] which use a much deeper neural network. Luong et al. [16]
achieves BLEU score of 19.00 with 4 layers deep Encoder-Decoder model. Shen et
al. [25] obtained the BLEU score of 18.02 with MRT techniques. For this work,
our Enc-Dec look-ahead attention NMT model with two layers achieves 20.36 BLEU
scores, which is on par with Zhou et al. [34] in term of BLEU. Note that Zhou
et al. [34] employ a much larger depth as well as vocabulary size to obtain
their best results.

##  5 Related Work

The recently proposed neural machine translation has drawn more and more
attention. Most of the existing approaches and models mainly focus on
designing better attention models [16, 19, 20, 28, 18], better strategies for
handling rare and unknown words [17, 14, 24], exploiting large-scale
monolingual data [3, 23, 33], and integrating SMT techniques [25, 7, 35, 30].

Our goal in this work is to design a smart attention mechanism to model the
dependency relationship between target words. Tu et al. [28] and Mi et al.
[19] proposed to extend attention models with a coverage vector in order to
attack the problem of repeating and dropping translations. Cohn et al. [6]
augmented the attention model with well-known features in traditional SMT.
Unlike previous works that attention models are mainly designed to predict the
alignment of a target word with respect to source words, we focus on
establishing a direct bridge to capture the long-distance dependency
relationship between target words. In addition, Wu et al. [31] lately proposed
a sequence-to-dependency NMT method, in which the target word sequence and its
corresponding dependency structure are jointly constructed and modeled.
However, the target dependency tree references are needed for training in this
model and our proposed model does not need extra resources.

Very Recently, Vaswani et al. [29] proposed a new simple network architecture,
Transformer, based solely on attention mechanisms with multi-headed self
attention. Besides, Lin et al. [15] presented a self-attention mechanism which
extracts different aspects of the sentence into multiple vector
representations. And the self-attention model has been used successfully in
some tasks including abstractive summarization and reading comprehension[22,
2]. Here, in order to alleviate the burden of LSTM to carry on the target-side
long-distance dependencies of NMT, we propose to integrate the look-ahead
attention mechanism into the conventional attention-based NMT which is used in
conjunction with a recurrent network.

##  6 Conclusion

In this work, we propose a novel look-ahead attention mechanism for generation
in NMT, which aims at directly capturing the long-distance dependency
relationship between target words. The look-ahead attention model not only
aligns to source words, but also refers to the previous generated words when
generating the next target word. Furthermore, we present and investigate three
patterns to integrate our proposed look-ahead attention into the conventional
attention model. Experiments on Chinese-to-English and English-to-German
translation tasks show that our proposed model obtains significant BLEU score
gains over strong SMT baselines and a state-of-the-art NMT baseline.

## Acknowledgments

The research work has been funded by the Natural Science Foundation of China
under Grant No. 61673380, No. 61402478 and No. 61403379.

## References

  * [1] Bahdanau, D., Cho, K., Bengio, Y.: Neural machine translation by jointly learning to align and translate. In Proceedings of ICLR 2015 (2015)
  * [2] Cheng, J., Dong, L., Lapata, M.: Long short-term memory-networks for machine reading. arXiv preprint arXiv:1601.06733 (2016)
  * [3] Cheng, Y., Xu, W., He, Z., He, W., Wu, H., Sun, M., Liu, Y.: Semi-supervised learning for neural machine translation. In Proceedings of ACL 2016 (2016)
  * [4] Chiang, D.: A hierarchical phrase-based model for statistical machine translation. In Proceedings of ACL 2005 (2005)
  * [5] Cho, K., van Merrienboer, B., Gulcehre, C., Bahdanau, D., Bougares, F., Schwenk, H., Bengio, Y.: Learning phrase representations using RNN encoder Cdecoder for statistical machine translation. In Proceedings of EMNLP 2014 (2014)
  * [6] Cohn, T., Hoang, C.D.V., Vymolova, E., Yao, K., Dyer, C., Haffari, G.: Incorporating structural alignment biases into an attentional neural translation model. arXiv preprint arXiv:1601.01085 (2016)
  * [7] He, W., He, Z., Wu, H., Wang, H.: Improved neural machine translation with SMT features. In Proceedings of AAAI 2016 (2016)
  * [8] Hochreiter, S., Schmidhuber, J.: Long short-term memory, vol. 9. MIT Press (1997)
  * [9] Junczys-Dowmunt, M., Dwojak, T., Hoang, H.: Is neural machine translation ready for deployment? A case study on 30 translation directions. In Proceedings of IWSLT 2016 (2016)
  * [10] Kalchbrenner, N., Blunsom, P.: Recurrent continuous translation models. In Proceedings of EMNLP 2013 (2013)
  * [11] Koehn, P., Hoang, H., Birch, A., Callison-Burch, C., Federico, M., Bertoldi, N., Cowan, B., Shen, W., Moran, C., Zens, R., et al.: Moses: Open source toolkit for statistical machine translation. Association for Computational Linguistics (2007)
  * [12] Koehn, P., Knowles, R.: Six challanges for neural machine translation. arXiv preprint arXiv:1706.03872 (2017)
  * [13] Koehn, P., Och, F.J., Marcu, D.: Statistical phrase-based translation. In Proceedings of ACL-NAACL 2013 (2003)
  * [14] Li, X., Zhang, J., Zong, C.: Towards zero unknown word in neural machine translation. In Proceedings of IJCAI 2016 (2016)
  * [15] Lin, Z., Feng, M., Santos, C.N.d., Yu, M., Xiang, B., Zhou, B., Bengio, Y.: A structured self-attentive sentence embedding. arXiv preprint arXiv:1703.03130 (2017)
  * [16] Luong, M.T., Pham, H., Manning, C.D.: Effective approaches to attention-based neural machine translation. In Proceedings of EMNLP 2015 (2015)
  * [17] Luong, M.T., Sutskever, I., Le, Q.V., Vinyals, O., Zaremba, W.: Addressing the rare word problem in neural machine translation. In Proceedings of ACL 2015 (2015)
  * [18] Meng, F., Lu, Z., Li, H., Liu, Q.: Interactive attention for neural machine translation. In Proceedings of COLING 2016 (2016)
  * [19] Mi, H., Sankaran, B., Wang, Z., Ge, N., Ittycheriah, A.: A coverage embedding model for neural machine translation. In Proceedings of EMNLP 2016 (2016)
  * [20] Mi, H., Wang, Z., Ge, N., Ittycheriah, A.: Supervised attentions for neural machine translation. In Proceedings of EMNLP 2016 (2016)
  * [21] Papineni, K., Roukos, S., Ward, T., Zhu, W.: Bleu: a methof for automatic evaluation of machine translation. In Proceedings of ACL 2002 (2002)
  * [22] Paulus, R., Xiong, C., Socher, R.: A deep reinforced model for abstractive summarization. arXiv preprint arXiv:1705.04304 (2017)
  * [23] Sennrich, R., Haddow, B., Birch, A.: Improving neural machine translation models with monolingual data. In Proceedings of ACL 2016 (2016)
  * [24] Sennrich, R., Haddow, B., Birch, A.: Neural machine translation of rare words with subword units. In Proceedings of ACL 2016 (2016)
  * [25] Shen, S., Cheng, Y., He, Z., He, W., Wu, H., Sun, M., Liu, Y.: Minimum risk training for neural machine translation. In Proceedings of ACL 2016 (2016)
  * [26] Sutskever, I., Vinyals, O., Le, Q.V.: Sequence to sequence learning with neural networks. In Proceedings of NIPS 2014 (2014)
  * [27] Tu, Z., Liu, Y., Lu, Z., Liu, X., Li, H.: Context gates for neural machine translation. arXiv preprint arXiv:1608.06043 (2016)
  * [28] Tu, Z., Lu, Z., Liu, Y., Liu, X., Li, H.: Modeling coverage for neural machine translation. In Proceedings of ACL 2016 (2016)
  * [29] Vawani, A., Shazeer, N., Parmar, N., Uszkoreit, J., Jones, L., N.Gomez, A., Kaiser, L., Polosukhin, I.: Attention is all you need. arXiv preprint arXiv:1706.03762 (2016)
  * [30] Wang, X., Lu, Z., Tu, Z., Li, H., Xiong, D., Zhang, M.: Neural machine translation advised by statistical machine translation. In Proceedings of AAAI 2017 (2017)
  * [31] Wu, S., Zhang, D., Yang, N., Li, M., Zhou, M.: Sequence-to-dependency neural machine translation. In Proceedings of ACL 2017 (2017)
  * [32] Zhai, F., Zhang, J., Zhou, Y., Zong, C., et al.: Tree-based translation without using parse trees. In Proceedings of COLING 2012 (2012)
  * [33] Zhang, J., Zong, C.: Exploiting source-side monolingual data in neural machine translation. In Proceedings of EMNLP 2016 (2016)
  * [34] Zhou, J., Cao, Y., Wang, X., Li, P., Xu, W.: Deep recurrent models with fast-forward connections for neural machine translation. arXiv preprint arXiv:1606.04199 (2016)
  * [35] Zhou, L., Hu, W., Zhang, J., Zong, C.: Neural system combination for machine translation. In Proceedings of ACL 2017 (2017)


# A Testability Analysis Framework for Non-Functional Properties

Michael Felderer
Bogdan Marculescu  Blekinge Institute of Technology
Karlskrona, Sweden
<EMAIL_ADDRESS>Francisco Gomes de Oliveira Neto
Robert Feldt
Richard Torkar  Chalmers and the University of Gothenburg
Gothenburg, Sweden

###### Abstract

This paper presents background, the basic steps and an example for a
testability analysis framework for non-functional properties.

###### Index Terms:

testability, extra-functional properties, non-functional properties,
robustness, software testing

##  I Introduction

Testability is a quality attribute that evaluates the effectiveness and
efficiency of testing: If the testability of a software artifact is high, then
finding faults by means of testing is easier. A lower degree of testability
results in increased test effort, and thus in less testing performed for a
fixed amount of time [1].

While software testability has been extensively investigated—in a recent
systematic literature review the authors identified 208 papers [2]—the focus
has always been on functional testing, while non-functional properties are
often neglected [3]. Little is known regarding testability of non-functional
properties. Thus, there is ample opportunity to investigate the relationship
between software testability and different non-functional properties. In this
paper we contribute to this unexplored field by characterising and
exemplifying a testability analysis framework for non-functional properties.
The aim of such an analysis framework is to predict and allocate test
resources, assist in the testability design, compare testing approaches or,
more generally, to support decision making in projects. The framework is
developed based on an in-depth analysis of available testability definitions,
testability frameworks and work testability of non-functional properties.

##  II Background and Related Approaches

In this section, we present background on testability definitions, related
testability measurement frameworks as well as related work on software
testability and non-functional properties. From each part of the section, we
draw some conclusions (shown in boxes at the end of each subsection) to guide
the development of testability measurement frameworks for non-functional
properties.

###  II-A Testability Definitions

Software testability is now established to be a distinct software quality
characteristics [4]. However, testability has always been an elusive, context-
sensitive concept and its correct measurement is a difficult exercise [5].
Therefore, the notion of software testability has been subject to a number of
different interpretations by standards and experts. In their systematic review
on software testability, Garousi et al. [2] provide, overall, 33 definitions
for testability extracted from different papers and standards.

A comprehensive testability definition is provided in the ISO/IEC Standard
25010 on system and software quality models. It defines testability as the
_degree of effectiveness and efficiency with which test criteria can be
established for a system, product or component and tests can be performed to
determine whether those criteria have been met_. The definition refers to the
effectiveness and efficiency aspects of testability and makes explicit that
testability is context-dependent with respect to the applied test criteria and
the relevant artifacts under test.

Some testability definitions explicitly cover the efficiency aspect, e.g.,
when defining testability as _the effort required to test software_ [6], or
the effectiveness aspect, e.g., _measure of how easily software exposes faults
when tested_ [7].

Other testability definitions define it explicitly via the core testability
factors of observability and controllability, e.g., when defining (domain)
testability as _ease of modifying a program so that it is observable and
controllable_ [8] .

Finally, there are also testability definitions that provide a more holistic
view and also take human and process aspects of testability into account. This
is for instance the case in the testability definitions _how easy it is to
test by a particular tester and test process, in a given context_ [9] and
_property of both the software and the process and refers to the easiness for
applying all the [testing] steps and on the inherent of the software to reveal
faults during testing_ [10].

  * TD1

Testability is relative to the test criteria and artifacts under test.

  * TD2

Testability is determined by effectiveness and efficiency measures for
testing.

  * TD3

Testability has product, process and human aspects.

###  II-B Available Testability Measurement Frameworks

Most available work on testability provides specific techniques or methods
[2]. But also models, metrics and frameworks are available. In this section,
we summarise three relevant and representative empirical frameworks for
testability based on the collection provided in [2] that support testability
measurement.

Binder [11] provides a testability framework for object-oriented systems. In
[11] the author claims that testability is a result of six high-level factors:
(1) Characteristics of the representation, (2) characteristics of the
implementation, (3) built-in test capabilities, (4) the test suite, (5) the
test support environment, and (6) the software development process. Each
factor is further refined to sub-characteristics, for which occasionally also
metrics and relationships are defined. For instance, structure is one sub-
characteristic of implementation with assigned complexity metrics like number
of methods per class.

Mouchawrab et al. [5] provide a well-founded measurement framework for object-
oriented software testability. The main aim of the framework is to improve
testability during software design based on UML diagrams. For each testing
phase, i.e., unit, integration, system, and regression testing, attributes
that potentially have an impact on software testability in that phase, are
provided. For each testability attribute, a list of measurable sub-attributes
is defined. For instance, for unit testing the testability attribute unit size
with the metrics local features and inherited features (measured for class
diagrams) is defined. The framework is complemented by a theory and its
associated hypotheses. For instance, one hypothesis states that _increasing
the number of local features to be tested increases the cost of unit testing
as more test cases are likely to be required and oracles may increase in
complexity if they need to account for additional attributes_.

Bach [9] defines five ‘practical’ testability types, i.e., epistemic
testability (“How narrow is the gap between what we know and what we need to
know about the status of the product under test”), value-related testability
(“Testability influenced by changing the quality standard or our knowledge of
it”), project-related testability (“Testability influenced by changing the
conditions under which we test”), intrinsic testability (“Testability
influenced by changing the product itself”), and subjective testability
(“Testability influenced by changing the tester or the test process”). For
each testability type, characteristics are defined, e.g., domain knowledge or
testing skills for subjective testability, and observability and
controllability for intrinsic testability. Furthermore, relationships like
_improving test strategy might decrease subjective testability or vice versa_
are defined.

None of the available testability frameworks examines testability, and its
relationship to other non-functional properties, in any details. However, we
can draw some conclusions to guide the development of testability analysis
frameworks:

  * TF1

Testability frameworks define testability characteristics and respective
metrics for a specific testability context.

  * TF2

Testability frameworks define statements to put the testability context,
characteristics and metrics in relations to each other.

###  II-C Software Testability and Non-Functional Properties

As highlighted before, software testability and their relationship to non-
functional properties is a relatively unexplored field. However, recently two
literature reviews on software testability and its relationship to the non-
functional properties robustness [3] and performance [12] were published.

The literature review on software testability and robustness includes overall
27 primary studies. The most frequently addressed testability issues
investigated in the context of robustness are observability, controllability,
automation, and testing effort. The most frequently addressed robustness
issues are fault tolerance, handling external influence, and exception
handling. Metrics that consider testability and robustness together are rare.
In general authors report a positive relationship between software testability
and software robustness [3].

The literature review on software testability and performance includes overall
26 primary studies. The most frequently addressed testability issues
investigated in the context of performance are observability, controllability,
automation, and testing effort. Note that the most frequently addressed
testability issues in the context of robustness and performance are identical.
The most frequently addressed performance issues are timeliness, response
time, and memory usage. Again metrics that consider testability and
performance together are rare. Furthermore, González et al. [13] present a
measurement framework for runtime testability of component-based systems that
is related to testability and performance. As runtime testing is, different
from traditional testing, performed on the final execution environment it
interferes with the system state or resource availability. The framework
therefore identifies the test sensitivity characteristics: component state,
component interaction, resource limitations and availability, which determine
whether testing interferes with the state of the running system or its
environment in an unacceptable way as well as the test isolation techniques
state separation, interaction separation, resource monitoring and scheduling
that provide countermeasures for its test sensitivity.

  * TN1

The most frequently addressed testability issues for robustness and
performance are observability, controllability, automation, and testing
effort.

  * TN2

The most frequently addressed robustness issues are fault tolerance, handling
external influence, and exception handling.

  * TN3

The most frequently addressed performance issues are timeliness, response
time, and memory usage.

##  III Towards a Measurement Framework for Non-Functional Testability

In this section, we first present goals of a measurement framework for non-
functional properties and then sketch our Testability Causation Analysis
Framework taking findings from the previous section into account.

###  III-A Overview and Goals

Our goal is to develop a measurement framework for non-functional properties
based on the findings of the previous section. As testability is a relative
concept (see TD1) and has different aspects (see TD3), it is not possible to
develop a single measurement system that covers all non-functional properties,
aspects and contexts. We need a general framework that can be adapted to these
points of variation and be instantiated to provide guidance to conceptualise,
analyse and measure testability in specific situations.

Available frameworks that have been successfully applied and evaluated for
functional testability analysis often take a layered approach and add detail
for a specific testability context, set of characteristics and related
variables (see TF1). Based on our analysis of existing frameworks above, we
adapt and extend the object-oriented testability framework (OOTF) of
Mouchawrab et al. [5] to address testability of non-functional properties.
Their framework is practical and can be used both for approximate, qualitative
assessment of testability (‘Would testability increase or decrease, given a
certain change?’), and as a basis for more exact, quantitative assessment
(‘How much will testability increase or decrease given a change of this size
in this variable?’). A basic assumption it makes is also that the cost to test
to a certain level of quality is a natural and hands-on way to conceptualise
testability. We thus reuse some aspects of the framework while adapting,
extending and generalising it so that it can be applied not only during the
analysis and design stages of object-oriented software but for analysis of
non-functional properties on any type of software system.

The reusable elements include the different levels and the decomposition of
testability into characteristics, sub-characteristics and attributes. That
allows the OOTF framework to be adapted towards specific conditions of
testability [5]. However, it is not obvious that non-functional (NF)
properties can be captured in this way.

For example, the OOTF framework distinguishes the different levels of testing
(unit, integration, system and regression), thus aggregating attributes from
lower levels into the higher levels. That distinction between levels of
testing is harder to make, or even not needed, when dealing with NF
properties, since NF testing not always apply or differ at all levels of
testing. Moreover, the OOTF framework does not clearly include factors that
account for other aspects of testability such as process, company/environment,
or the considered testing techniques.

To summarise, our contributions relative to the existing framework, are four-
fold: $i$) To generalise from OO software to any type of software system,
$ii$) to focus on non-functional testability rather than functional, $iii$) to
clarify that the same framework can be used both qualitatively and
quantitatively, and $iv$) to consider more types of factors of the situation
than only design-related factors of the SUT. In the following, we further
detail our proposed framework called Testability Causation Analysis Framework.

###  III-B TCAF: Testability Causation Analysis Framework

TCAF is mostly to be used qualitatively but we see a natural extension to also
quantitative use. Our adaptation focuses on analysing testability in terms of
the inputs that mediate or directly affect it (e.g., SUT, the test
technique(s) being used, human and organisational facets, etc.) and their
effects on testability outputs (primarily the cost and effectiveness of
testing111Note that we explicitly exclude efficiency here, since it can be
defined as effectiveness divided by cost and is thus indirectly being analysed
via its sub-components.).

For testability outputs, we argue that NF properties are typically not atomic
and need to be broken down into sub-characteristics or issues. This allows a
more detailed analysis. For instance, if we choose Robustness as the NF
property, there are the sub-characteristics identified in the literature
review of Hassan et al. [3], i.e., exception handling, fault tolerance, and
handling of external influences. Depending on the specific NF property and
level of detail one wants, these might need to be further sub-divided into
characteristics. Once this division has been made we have identified a set of
NF attributes. For each attribute we then identify specific testability
outputs.

An underlying aspect of testability is to measure the time/effort/cost needed
to perform a certain type of testing [6, 5], which we will refer simply as
TestCost. Therefore, all NF sub-characteristics should be connected to a cost
variable. Conversely, in order to capture effectiveness, i.e. the (quality)
level to which the testing of the NF (sub-)characteristic has been achieved,
we need attribute-specific variables that will often vary depending on a
variety of factors. We refer to those attribute-specific variables as the
extent of testability, or simply TestabilityExtent.

Note that, in some contexts, the extent can be a binary variable where
stakeholders do (or do not) have the necessary instruments and dependencies to
test the NF attribute, i.e., it is not necessarily continuous. Other scenarios
can be a degree of the extent to which testability can be measured (similar to
coverage variables). For instance, a situation where a test technique can only
be partially applied would mean a reduced extent of the measured testability.
A typical example would be when there is a fixed time or cost for conducting a
certain type of testing.

In brief, our framework thus decomposes testability into several levels,
beginning with the non-functional property of interest and then further into,
potentially, several levels of sub-characteristics to arrive at the NF
attributes we consider. Each such NF attribute is then connected to
testability output variables (TOVs), i.e., TestCost and TestabilityExtent,
that capture aspects of the testability factors in terms of cost and extent of
testing. The main idea of TCAF is then to consider which input factors that
would cause a change in these NF TOVs. These input factors are captured in
testability input variables (TIVs) that are typically of at least three types:
those that capture $i$) the surrounding environment, namely the context (e.g.,
team configuration, processes used, experience with the used test techniques),
$ii$) the system under test (e.g., system complexity, number of test
interfaces, number of arguments and types of those interfaces), and $iii$) the
test techniques considered (e.g., test optimisation and test generation).
Given input factors and the output factors they (potentially) affect how one
can then proceed to qualitatively analyse the direction and strength of this
causation, or to model it statistically and thus being able to predict those
effects.

The following steps further detail how to use the TCAF framework:

  1. 1.

Identify Testability Output Variables (TOVs) specific to the non-functional
property considered and its different sub-characteristics. These variables
will always include the TestCost variable, but can also have TestabilityExtent
variables. Outputs: Layered decomposition of the NF property into NF
attributes and testability output variables for each of the attributes.

  2. 2.

Identify the set of test techniques to be considered or compared in terms of
testability. If it is already given that a certain technique can only reach a
certain degree of TestabilityExtent for an NF attribute, they need not be
further modelled in subsequent steps. If the test techniques imply specific
sub-activities in order to be applied refine the TestCost variables from Step
1 to be specific for each sub-activity (designing, executing, reporting the
tests, etc.).

  3. 3.

Identify system and context attributes that have an impact on TOVs, and define
TIVs for them. The test techniques themselves might also have variation points
that lead to additional TIVs to include.

  4. 4.

Analyse the effect that TIVs have on TOVs. This can either happen
Qualitatively or Quantitatively. For the latter, we need quantification of TIV
values as well as statistical modelling of the TOVs based on the TIVs. For the
former, one needs experience- or research-based reasoning of the level or
direction of effect.

We believe that the TCAF framework can help build a causal model of how
different attributes/variables of the TIV (e.g., context/SUT/test techniques)
determine different aspects of testability in terms of TOVs, i.e., very much
how it has been done in other disciplines [14]. An added benefit is to be able
to quantify those variables and, eventually, statistically model the strength
of their effect on testability. Given recent progress on actually analysing
causality, rather than simply correlating variables with statistical methods,
this would now be realistic [15]. This feature would be highly relevant and
useful for estimating/predicting the TOVs related to cost, while it may be
harder to quantify and then predict TOVs measuring the testability extent.

##  IV Example Application: Robustness Testing

This section sketches an example of how TCAF can be applied for testing
robustness. An overview of the relevant TIVs is shown in Figure 1.

Figure 1: Testability causation analysis example, focusing on robustness.

In the following, we explain each of the four steps to instantiate TCAF.

Step 1: Testability output variables. For this example we will focus on
robustness. For the sake of brevity, we only consider two exception handling
sub-characteristics of robustness, the system’s ability to handle atypical and
invalid inputs. The TOVs are the cost for and extent to which we can test the
two NF attributes: CostAtypical, ExtentAtypical, CostInvalid, ExtentInvalid.

Step 2: Test technique. We consider a single test technique in this example:
GödelTest, a search-based, automated test data generation technique. GödelTest
[16] has been shown to be useful for robustness testing [17]. It defines a
method of developing valid test inputs of any complexity using a _generator_ ,
to explore invalid test data using one or more _mutation operators_ , all
driven by a _distance metric_ to assess how “far away” the generated inputs
are from the typical test cases. Each of the three components (generator,
mutation operators, distance metric) needs to be in place for the technique to
work, so the TestCost associated with each will be assessed separately. When
applying this test technique to a large software under test (SUT) we can
further consider all these factors for each and every of the interfaces of the
SUT that we want to test for robustness, but for the sake of this example we
only consider one interface.

Step 3: System and context variables. An example of a context attribute that
would have an impact on the cost of adopting the technique is that of the
relative experience that the company and its testers and developers have with
automated testing tools in general, and with search-based software testing
(SBST) tools and GödelTest, in particular. The more experienced the testers
and developers are, and the more experienced the company is in developing and
using automated testing tools, the lower the costs are likely to be. In
addition, the complexity of the SUT is also likely to be an important factor.
For example, cost is likely to increase with the number and relative
complexity of input data types. For example, it is clear that it is much
easier to define a generator for arrays of integers than for graphs
represented in XML files.

Step 4: Causal effects. The effects can be analyzed depending on the amount of
information available, and this analysis can be updated in time. An initial
evaluation would most likely be qualitative, focusing on whether each of the
TIVs has an effect, and if that effect is likely to be positive or negative. A
company may conclude that it does not have many testers or developers with
SBST experience, and that is likely to have a negative impact on the cost of
adopting GödelTest. Or it might decide that applying robustness testing on all
interfaces is not called for and the testing needs to be more focused. As more
information becomes available, the analysis can be more refined, first as a
qualitative analysis focusing on discrete steps. For example, when looking at
the components of GödelTest, the company may conclude that it has a number of
testing tools that allow the generation of inputs for their SUTs. Thus,
_generators_ are available for a relatively low cost. On the other extreme,
mutation operators would likely be custom, incurring significant cost to
develop and validate; in particular, if the input data types are complex and
company- or system-specific.

While the analysis for CostAtypical and CostInvalid should be quite similar
there is a difference in the number and type of mutation operators needed; the
mutation operators for generating atypical inputs are much less complex since
we are using the generator as is (atypical inputs are still valid and thus
should be captured in the way the generator is defined). Similarly, there are
many more invalid data than valid, and thus atypical, so ExtentInvalid will
have to be much more constrained and will directly affect CostInvalid. This
indicates that more complex analysis or statistical modeling might be needed.
It is not always the case that testability outputs can be predicted only from
the inputs; outputs might sometimes influence each other.

When possible, the analysis would move more toward quantitative assessments
and to include more attributes and factors. For robustness, we could consider
other robustness aspects from the literature [18] as well. A company with
experience in working with SBST systems, for example, may be able to estimate
the cost of implementing GödelTest quite accurately, as well as have a clearer
understanding of the effect the implementation would have on its products.
However, regardless of the level of detail used, TCAF can help structure the
testability analysis and make it concrete.

##  V Conclusion

In this paper we present a testability causation analysis framework for non-
functional properties. The framework is developed based on available
frameworks and review studies on testability, and prototypically applied to
robustness testing.

The framework is used in four steps. First, testability output variables
including test cost and testability extend are identified. Second, the set of
test techniques to be considered is identified. Third, system and context
attributes are identified as testability input variables. Fourth, the effect
that testability input variables have on testability output variables are
analysed.

So far the framework has not been evaluated. In future, we therefore plan to
refine and evaluate the testability causation analysis framework for different
non-functional properties including robustness, performance, security and
energy consumption (as well as their inter-dependence) in different contexts.

## Acknowledgment

The paper was partly funded by the Knowledge Foundation (KKS) of Sweden
through the project 20130085: Testing of Critical System Characteristics
(TOCSYC).

## References

  * [1] J. M. Voas and K. W. Miller, “Software testability: The new verification,” _IEEE software_ , vol. 12, no. 3, pp. 17–28, 1995.
  * [2] V. Garousi, M. Felderer, and F. Nur Kilicaslan, “What we know about software testability: A survey,” _ArXiv e-prints_ , Jan. 2018.
  * [3] M. M. Hassan, W. Afzal, M. Blom, B. Lindström, S. F. Andler, and S. Eldh, “Testability and software robustness: A systematic literature review,” in _Proceedings of the 41st Euromicro Conference on Software Engineering and Advanced Applications (SEAA)_. IEEE, 2015, pp. 341–348.
  * [4] ISO/IEC, “ISO/IEC 25010:2011 systems and software engineering – Systems and software quality requirements and evaluation (square) – System and software quality models,” 2011.
  * [5] S. Mouchawrab, L. C. Briand, and Y. Labiche, “A measurement framework for object-oriented software testability,” _Information and software technology_ , vol. 47, no. 15, pp. 979–997, 2005.
  * [6] ISO/IEC/IEEE, “ISO/IEC/IEEE 24765:2010 Systems and software engineering – Vocabulary,” 2010.
  * [7] T. Yu, W. Wen, X. Han, and J. H. Hayes, “Predicting testability of concurrent programs,” in _Proceedings of the 10th IEEE International Conference on Software Testing, Verification and Validation (ICST)_. IEEE, 2016, pp. 168–179.
  * [8] R. Poston, J. Patel, and J. S. Dhaliwal, “A software testing assessment to manage project testability,” in _Proceedings of the 20th European Conference on Information Systems (ECIS)_ , 2012, pp. 219–.
  * [9] J. Bach. (1999) Heuristics of software testability. [Online]. Available: http://www.satisfice.com/tools/testability.pdf
  * [10] Y. Le Treon, D. Deveaux, and J.-M. Jézéquel, “Self-testable components: From pragmatic tests to design-for-testability methodology,” in _Proceedings of Technology of Object-Oriented Languages and Systems_. IEEE, 1999, pp. 96–107.
  * [11] R. V. Binder, “Design for testability in object-oriented systems,” _Communications of the ACM_ , vol. 37, no. 9, pp. 87–101, 1994.
  * [12] M. M. Hassan, W. Afzal, B. Lindström, S. M. A. Shah, S. F. Andler, and M. Blom, “Testability and software performance: A systematic mapping study,” in _Proceedings of the 31st Annual ACM Symposium on Applied Computing_. ACM, 2016, pp. 1566–1569.
  * [13] A. González, E. Piel, and H.-G. Gross, “A model for the measurement of the runtime testability of component-based systems,” in _Software Testing, Verification and Validation Workshops (ICSTW)_. IEEE, 2009, pp. 19–28.
  * [14] G. Imbens and D. Rubin, _Causal Inference in Statistics, Social, and Biomedical Sciences_ , ser. Causal Inference for Statistics, Social, and Biomedical Sciences: An Introduction. Cambridge University Press, 2015.
  * [15] J. Peters, D. Janzing, and B. Schölkopf, _Elements of Causal Inference: Foundations and Learning Algorithms_ , ser. Adaptive Computation and Machine Learning Series. Cambridge, MA, USA: The MIT Press, 2017.
  * [16] R. Feldt and S. Poulding, “Finding test data with specific properties via metaheuristic search,” in _2013 IEEE 24th International Symposium on Software Reliability Engineering (ISSRE)_ , Nov 2013, pp. 350–359.
  * [17] S. Poulding and R. Feldt, “Generating controllably invalid and atypical inputs for robustness testing,” in _2017 IEEE International Conference on Software Testing, Verification and Validation Workshops (ICSTW)_ , March 2017, pp. 81–84.
  * [18] A. Shahrokni and R. Feldt, “A systematic review of software robustness,” _Information and Software Technology_ , vol. 55, no. 1, pp. 1–17, 2013.