∎

11institutetext: Caio J. B. V. Guimarães, 22institutetext: Laboratory of
Machine Learning and Intelligent Instrumentation, Federal University of Rio
Grande do Norte, Natal 59078-970, Brazil.
ORCiD: 0000-0002-8392-5556
22email<EMAIL_ADDRESS>
Marcelo A. C. Fernandes, 33institutetext: Department of Computer Engineering
and Automation, Federal University of Rio Grande do Norte, 59078-970, Natal,
RN, Brazil.
ORCiD: 0000-0001-7536-2506
33email<EMAIL_ADDRESS>

# Real-time Neural Networks Implementation Proposal for Microcontrollers

Caio J. B. V. Guimarães and Marcelo A. C. Fernandes

(Received: date / Accepted: date)

###### Abstract

The adoption of intelligent systems with Artificial Neural Networks (ANNs)
embedded in hardware for real-time applications currently faces a growing
demand in fields like the Internet of Things (IoT) and Machine to Machine
(M2M). However, the application of ANNs in this type of system poses a
significant challenge due to the high computational power required to process
its basic operations. This paper aims to show an implementation strategy of a
Multilayer Perceptron (MLP) type neural network, in a microcontroller (a low-
cost, low-power platform). A modular matrix-based MLP with the full
classification process was implemented, and also the backpropagation training
in the microcontroller. The testing and validation were performed through
Hardware in the Loop (HIL) of the Mean Squared Error (MSE) of the training
process, classification result, and the processing time of each implementation
module. The results revealed a linear relationship between the values of the
hyperparameters and the processing time required for classification, also the
processing time concurs with the required time for many applications on the
fields mentioned above. These findings show that this implementation strategy
and this platform can be applied successfully on real-time applications that
require the capabilities of ANNs.

###### Keywords:

Neural Networks Microcontrollers Multi-Layer Perceptron real-time.

††journal: arXiv.org

##  1 Introduction

The microcontrollers ($\mu$Cs) have been applied in many areas: industrial
automation, control, instrumentation, consumer electronics, and other various
areas. Nonetheless, there is an ever-growing demand for these devices,
especially in emerging sectors like the Internet of Things (IoT), Smart Grid,
Machine to Machine (M2M) and Edge Computing.

A $\mu$C can be classified as programmable hardware platform that enables
Embedded System applications in specific cases. It is important to know that
$\mu$Cs are mainly composed of a General-Purpose Processor (GPP) of 8, 16 or
32 bits. Then this GPP is connected to some peripherals like Random Access
Memory (RAM), flash memory, counters, signal generators, communication
protocol specific hardware, analog to digital and digital to analog converters
and others.

An important fact is that on most products that are available today, the
$\mu$Cs embedded into them encapsulate an 8-bit GPP with enough computational
power and memory storage, to show itself as a resourceful platform for many
embedded applications. However, those same 8-bit $\mu$Cs are considered low-
power and low-cost platforms when compared with other platforms that are used
to implement AI applications with Artificial Neural Networks (ANNs) (19; 17).

The use of ANNs for embedded intelligent systems with real-time constraints
has been a recurrent research topic for many (10; 12; 16; 15; 11). A large
part of the works devised from this topic is driven by the growing demand for
AI techniques for IoT, M2M and Edge Computing applications.

A major problem with implementing ANN applications into embedded systems is
the computational complexity associated with ANNs. In regards to the Multi-
Layer Perceptron (MLP), described in this work, there are many inherent
multiplications and calculations of nonlinear functions (10; 12; 16). Besides
the feedforward process between the input and the synaptic weights, the MLP
also has a training algorithm associated with it to find the optimum weights
of the neural network. This training algorithm is very computationally
expensive (7). If the training process is also performed in real-time, the
computational complexity is increased several times. This increase in
complexity automatically raises the processing time and requirements for
memory storage from the hardware platform used in the application (10; 12;
16).

The use of MLP neural networks for real-time applications on $\mu$Cs it’s not
a new effort. The work (2) in which the authors describe a method to linearize
the nonlinear characteristics of many sensors using an MLP-NN on an 8-bit
PIC18F45J10 $\mu$C. The obtained results showed that if the network
architecture is right, even very difficult problems of linearization can be
solved with just a few neurons.

In (3), a fully-connected multi-layer ANN is implemented on a low-end and
inexpensive $\mu$C. Also, a pseudo-floating-point multiplication is devised,
to make use of the internal multiplier circuit inside the PIC18F45J10 $\mu$C
used. The authors managed to store 256 weights into the 1KB SRAM of the $\mu$C
and deemed it being enough for most embedded applications.

In (4) Farooq et al implemented a hurdle-avoidance system controller for a
car-like robot using an AT89C52 $\mu$C as a system embedding platform. They
implemented an MLP with a back-propagation training algorithm and a single
hidden layer. The proposed system was tested in various environments
containing obstacles and was found to avoid obstacles successfully.

The paper (14) presents a neural network that is trained with the
backpropagation (BP) algorithm and validated using a low-end and inexpensive
PIC16F876A 8-bit $\mu$C. The authors chose a chemical process as a realistic
example of a nonlinear system to demonstrate the feasibility and performance
of this approach, as well as the results found using the microcontroller,
against a computer implementation. With three inputs, five hidden neurons and
an output neuron on the MLP, the application showed complete suitability for a
$\mu$C-based approach. The results comparing the $\mu$C implementation showed
almost no difference in Mean Square Error (MSE) after 30 iterations of the
training algorithm.

The work presented in (20) an ANN-based PID controller is shown using an ARM9
based $\mu$C. The authors modeled the controller to overcome the nonlinearity
of a microbiologic fermentation process and to provide a better performing
control strategy. The results showed a more accurate control over the
controlled parameters with an ANN-PID an achieve a greater control performance
and ability of the system to meet the requirements.

In (6) the authors implemented a classification application for the MNIST
dataset. This implementation regards the 10 digits and full classification
with $99.15\%$ testing accuracy. Also, this is implemented with a knowingly
highly resource-hungry ANN model, the Convolutional Neural Network (CNN),
using less than $2KB$ of SRAM memory and also $6KB$ of program memory, FLASH.
This work was embedded on a Arduino Uno development kit that is comprised of a
breakout board for the 8-bit ATMega$328$p $\mu$C, with $32KB$ of program
memory and $2KB$ of work memory, running at $16MHz$.

The reference works presented above have shown different aspects of
implementing ANNs on $\mu$Cs. In (3; 4; 14) you will find application
proposals showing MLP-ANNs trained with the Backpropagation algorithm (BP)
implemented on $\mu$Cs with good results, but none of those talk about memory
usage and processing-time parameters that vary according to the MLP
hyperparameters. In (2; 13; 20) the authors presented some results regarding
processing-time, but none dependant on the number of artificial neurons or
even comparing the time required to train the ANN in real-time or not.

Therefore, this work proposes an implementation of an MLP-ANN that can be
trained with the BP algorithm into an ATMega2560 8-bit $\mu$C in the C
language, to show that many applications with ANNs are suitable on this $\mu$C
platform. We also present two implementations regarding a model that is
trained on the $\mu$C in real-time and another implementation that is trained
with Matlab and then ported to the same architecture to execute classification
in real-time.

In addition to the implementation proposal, parameters of processing time to
each feedforward step and backward steps in the training and classification
process are presented. Also, the variation of these parameters is shown due to
the variation of the hyperparameters of the MLP. We also validate the
classification and training results on a Hardware-in-the-Loop (HIL) strategy.

##  2 System Description

Figure 1 shows a block diagram detailing the modules implemented into the
$\mu$C. This implementation has the work (5) as a direct reference, that
models the MLP into a matrix form, simplifying and modularizing all the
feedforward and backwards propagations As seen in Figure 1, the MLP here
implemented is structured as four main modules, the Input Random Permutation
Module (IRPM), FeedForward Module (FFM-$k$), Error Module (EM) and
Backpropagation Module (BPM-$k$), at which the variable $k$ represents the ANN
layer. It is important to add that the implementation presented in this work
is shown with two layers (one hidden and the output layer), but it can be
easily extended for more. The modules and associated mathematical modeling
will be detailed in the following subsections.

Figure 1: Block diagram detailing the modules of the matrix implementation for
a MLP trained with BP algorithm.

###  2.1 Associated Variables

The implementation is composed of four main variables that are passed by
reference between the modules. These variables are the input signals matrix,
$\mathbf{Y}^{k=0}\left(n\right)$ defined as

$\mathbf{Y}^{0}\left(n\right)=\left[\mathbf{y}^{0}_{1}\left(n\right),\ldots,\mathbf{y}^{0}_{s}\left(n\right),\ldots,\mathbf{y}^{0}_{\mathbb{N}}\left(n\right)\right]$
(1)

where $k=0$ means that this matrix is dealing with the input layer of the MLP,
$n$ represents the iteration number of the training algorithm. $\mathbb{N}$ is
defined as the number os samples of a training set and $\mathbf{y}_{s}$ the
$s$-th sample defined as

$\mathbf{y}^{0}_{s}\left(n\right)=\left[y^{0}_{s1}\left(n\right),\ldots,y^{0}_{s}\left(n\right),\ldots,y^{0}_{P}\left(n\right)\right]^{T}$
(2)

where $P$ is the number of available inputs of the MLP. The synaptic weights
matrix from the $k$-th layer, $\mathbf{W}^{k}\left(n\right)$, is defined as

$\mathbf{W}^{k}\left(n\right)=\left[\begin{array}[]{ccccc}w_{10}^{k}\left(n\right)&\cdots&w_{1h}^{k}\left(n\right)&\cdots&w_{1H^{k-1}}^{k}\left(n\right)\\\
\vdots&\ddots&\vdots&\ddots&\vdots\\\
w_{j0}^{k}\left(n\right)&\cdots&w_{jh}^{k}\left(n\right)&\cdots&w_{jH^{k-1}}^{k}\left(n\right)\\\
\vdots&\ddots&\vdots&\ddots&\vdots\\\
w_{H^{k}0}^{k}\left(n\right)&\cdots&w_{H^{k}h}^{\left(y\right)}\left(n\right)&\cdots&w_{H^{k}H^{k-1}}^{k}\left(n\right)\end{array}\right],$
(3)

where $H^{k}$ is the number of neurons from the $k$-th layer and
$w_{ij}^{k}(n)$ represents the synaptic weight associated with the $i$-th
artificial neuron, from the $j$-th input signal of the $k$-th layer at the
$n$-th iteration. The output signals matrix, $\mathbf{Y}^{L}\left(n\right)$
defined as

$\mathbf{Y}^{L}\left(n\right)=\left[\mathbf{y}^{L}_{1}\left(n\right),\ldots,\mathbf{y}^{L}_{s}\left(n\right),\ldots,\mathbf{y}^{L}_{\mathbb{N}}\left(n\right)\right],$
(4)

where $L$ is the number of layers of the MLP and also defines which layer is
the last one. Where $y_{s}^{L}(n)$ represents the output signal associated
with the $s$-th sample input $y_{s}^{0}$ that is defined as

$\mathbf{y}^{L}_{s}\left(n\right)=\left[y^{L}_{1}\left(n\right),\ldots,y^{L}_{s}\left(n\right),\ldots,y^{L}_{M}\left(n\right)\right]^{T}$
(5)

where $M$ is the number of output neurons.

The $\mathbf{D}\left(n\right)$ variable represents the desired values or
labels of the training set composed of the $\mathbf{D}\left(n\right)$ and the
$\mathbf{Y}^{0}\left(n\right)$, that is defined as

$\mathbf{D}\left(n\right)=\left[\mathbf{d}_{1}\left(n\right),\mathbf{d}_{2}\left(n\right),\ldots,\mathbf{d}_{s}\left(n\right),\ldots,\mathbf{d}_{\mathbb{N}}\left(n\right)\right]$
(6)

where $\mathbf{d}_{s}\left(n\right)$ is the vector of desired values referring
to the $s$-th sample associated with the $y_{s}^{0}(n)$ input signal, that is
defined as

$\mathbf{d}_{s}\left(n\right)=\left[d_{1}\left(n\right),\ldots,d_{s}\left(n\right),\ldots,d_{M}\left(n\right)\right]^{T}.$
(7)

For an MLP with two layers, $\mathbf{W}^{1}\left(n\right)$ represents the
synaptic weights matrix from the hidden layer ($H^{0}=P$) and
$\mathbf{W}^{2}\left(n\right)$ is the weights matrix from the output layer
($H^{2}=M$) at the $n$-th iteration. In addition to those two matrices, a few
others are created to accommodate intermediary results from feedforward and
backward propagation operations of the MLP.

###  2.2 _Feedforward Module_ \- ($\text{FFM}-k$)

This module is responsible for running the feedforward operation of an MLP,
propagating the inputs through each $k$-th layer during each $n$-th iteration.
As most BP implementations, this proposal can operate in online mode or batch
mode (defining $\mathbb{N}>1$). At each $k$-th FFM-$k$ at each $k$-th layer
the following equation is calculated as

$\mathbf{Y}^{k}\left(n\right)=\varphi\left(\mathbf{W}^{k}\left(n\right)\mathbf{Y}^{k-1}\left(n\right)\right)$
(8)

where $\mathbf{Y}^{k-1}\left(n\right)$ is the output signals matrix from the
previous layer. The $\mathbf{Y}^{k}\left(n\right)$ represents the output of
the current layer and $\varphi\left(.\right)$ is the activation function of
the current $k$-th layer. As previously said a few other matrices are devised
as part of the BP calculation and some of them store these calculation results
from Equation 8.

Algorithm 1 describes the pseudocode executed when the FFM-$k$ module is
called. The function prodMatrix() implements the matrix product between
$\mathbf{W}^{k}\left(n\right)$ and $\mathbf{Y}^{k-1}\left(n\right)$ and in the
end it stores the product result in $\mathbf{Y}^{k}\left(n\right)$. The
actFun() function executes the activation function of the $k$-th layer to each
element of $\mathbf{Y}^{k}\left(n\right)$ and stores the result in itself
($\mathbf{Y}^{k}\left(n\right)$) as it runs.

Algorithm 1 Description of the algorithm implemented by the $\text{FFM}-k$
module.

1:function
$\text{FFM}-k$($\mathbf{W}^{k}\left(n\right)$,$\mathbf{Y}^{k-1}\left(n\right)$,$\mathbf{Y}^{k}\left(n\right)$)

2:
$\text{prodMat}\left(\mathbf{W}^{k}\left(n\right),\mathbf{Y}^{k-1}\left(n\right),\mathbf{Y}^{k}\left(n\right)\right)$

3: $\text{activfun}\left(\mathbf{Y}^{k}\left(n\right)\right)$

4:end function

###  2.3 _Error Module_ \- ($\text{EM}-k$)

The error module EM-$k$ calculates the error between the desired values matrix
$\mathbf{D}\left(n\right)$ and the output signals matrix
$\mathbf{Y}^{L}\left(n\right)$ of the last layer, $L$. The equation that is
evaluated at the EM-$k$ is defined as

$\mathbf{E}\left(n\right)=\mathbf{D}\left(n\right)-\mathbf{Y}^{L}\left(n\right)$
(9)

Algorithm 2 describes how the EM-$k$ module functions, in which the
difMatrix() function implements the element-by-element difference between
$\mathbf{D}\left(n\right)$ and $\mathbf{Y}^{L}\left(n\right)$ and stores the
result into the $\mathbf{E}\left(n\right)$ matrix.

Algorithm 2 Pseudocode implementation of the EM module.

1:function
EM($\mathbf{Y}^{L}\left(n\right)$,$\mathbf{D}\left(n\right)$,$\mathbf{E}\left(n\right)$)

2:
$\text{difMatrix}\left(\mathbf{Y}^{L}\left(n\right),\mathbf{D}\left(n\right),\mathbf{E}\left(n\right)\right)$

3:end function

###  2.4 _Backpropagation Module_ \- ($\text{BPM}-k$)

The last module is responsible for the main training part of the
implementation. The BPM-$k$ calculates the new updated values of the synaptic
weights matrices of the $L$ layers that better approximate the desired values,
$\mathbf{W}^{k}\left(n\right)$. The equation that the BPM-$k$ implements is
defined as

$\mathbf{W}^{\left(k\right)}\left(n+1\right)=\mathbf{W}^{\left(k\right)}\left(n\right)+\Delta\mathbf{W}^{\left(k\right)}\left(n\right)$
(10)

where

$\Delta\mathbf{W}^{\left(k\right)}\left(n\right)=\frac{\eta}{\mathbb{N}}\mathbf{g}^{k}\left(n\right)\left[\begin{array}[]{c}\mathbf{-1}\\\
\mathbf{Y}^{k-1}\left(n\right)\end{array}\right]^{T}+\alpha\mathbf{\Delta
W}^{\left(k\right)}\left(n-1\right),$ (11)

where $\eta$ is the learning-rate of the BP algorithm, $\alpha$ is the
learning-moment rate factor and $\mathbf{g}^{k}\left(n\right)$ is defined as

$\mathbf{g}^{k}\left(n\right)=\left\\{\begin{array}[]{ll}\text{prod}\left(\varphi^{\prime}\left(\mathbf{Y}^{k}\left(n\right)\right),\mathbf{E}\left(n\right)\right)&\text{
for }k=L\\\ \mathbf{z}^{k}\left(n\right)&\text{ for }1\leq
k<L\end{array}\right.$ (12)

where

$\mathbf{z}^{k}\left(n\right)=\text{prod}\left(\varphi^{\prime}\left(\left[\begin{array}[]{c}\mathbf{-1}\\\
\mathbf{Y}^{k}\left(n\right)\end{array}\right]\right),\left[\mathbf{W}^{\left(y\right)}\left(n\right)\right]^{T}\mathbf{g}^{\left(k+1\right)}\left(n\right)\right)$
(13)

and

$\mathbf{z}^{k}\left(n\right)=\left[\begin{array}[]{c}\begin{array}[]{cccc}z_{11}^{\left(k\right)}\left(n\right)&z_{12}^{\left(k\right)}\left(n\right)&\ldots&z_{1\mathbb{N}}^{\left(k\right)}\left(n\right)\end{array}\\\
\hline\cr\mathbf{z}^{\left(k\right)}\left(n\right)\end{array}\right].$ (14)

The prod() function in the Equation 13 implements an element-wise product
between two matrices, implemented in Algorithm 3, and
$\varphi^{\prime}(\cdot)$ is the derivative of the activation function.

###  2.5 Basic Operations

In this section, we describe how we implemented a few basic operations used in
this work. First, Algorithm 3 implements the matrix product. A very important
detail is that all the modules were implemented following pointer arithmetic
procedures. With this in mind, the source code is very optimized for memory
usage, reducing the overall duration of execution from each module. Every
matrix used in this implementation are floating-point (IEEE754) (1)
representation values.

Algorithm 3 Matrix product implementation pseudocode

1:function
$prodMat$($\mathbf{W^{k}},\mathbf{Y^{k-1}},\mathbf{Y^{k}},P,M,\mathbb{N}$)

2: Initialize ($i$, $j$, $s$, accumulate) $\leftarrow$ 0

3: for $i$ $\leftarrow$ 1 to M do

4: for $j$ $\leftarrow$ 1 to $\mathbb{N}$ do

5: accumulate $\leftarrow$ 0

6: for $s$ $\leftarrow$ 1 to P do

7: accumulate = accumulate + $\mathbf{W^{k}}$[$i$][$s$]$\times$
$\mathbf{Y^{k-1}}$[$s$][$j$]

8: end for

9: $\mathbf{Y^{k}}$[$i$][$j$] = accumulate

10: end for

11: end for

12:end function

Algorithm 4 shows the pseucode of a element-wise product between two matrices
used in this work, more specifically in the BPM-$k$ module implementation.
This same pseudocode in Algorithm 4 can be slightly altered to perform
subtraction or addition by editing the operation between matrices on line $5$.
It’s important to notice that Algorithm 4 requires that both matrices have the
same dimensions.

Algorithm 4 Element-wise matrix product implementation algorithm.

1:function $prod$($\mathbf{Y^{k}},\mathbf{E},\mathbf{g^{k}},P,M$)

2: Initialise ($i$, $j$) $\leftarrow$ 0

3: for $i$ $\leftarrow$ 1 to P do

4: for $j$ $\leftarrow$ 1 to M do

5: $\mathbf{g^{k}}$[$i$][$j$] =
$\mathbf{Y^{k}}$[$i$][$j$]$\times$$\mathbf{E}$[$i$][$j$]

6: end for

7: end for

8:end function

Algorithm 5 presents to us the implementation of the calculation of the Trace
and Product between two matrices at a single operation inside a nested loop.
This simple optimization saved a few $\mu$s of processing time for the overall
training process.

Algorithm 5 Pseudocode implementation of the trace of the product between two
matrices.

1:function $trace$($\mathbf{E^{k}},\mathbf{E^{kT}},P,M$)

2: Initialize ($i$, $j$,trace) $\leftarrow$ 0

3: for $i$ $\leftarrow$ 1 to P do

4: for $j$ $\leftarrow$ 1 to M do

5: trace = trace + $\mathbf{E^{k}}$[$i$][$j$]$\times$
$\mathbf{E^{k}T}$[$i$][$j$]

6: end for

7: end for

8:end function

Algorithm 6 shows the implemented steps for calculating the activation
function of the induced-local-field of each neuron, an element-wise operation.
This Algorithm 6 is implementing a sigmoid activation function.

Algorithm 6 Pseudocode implementation of the sigmoid activation function

1:function $activfun$($\mathbf{Y^{k}},\mathbf{Y^{k+1}},P,M$)

2: Initialise ($i$, $j$) $\leftarrow$ 0

3: for $i$ $\leftarrow$ 1 to P do

4: for $j$ $\leftarrow$ 1 to M do

5:
$\mathbf{y^{k+1}}$[$i$][$j$]=(1.0)/(1.0+exponential(-$\mathbf{Y^{k}}$[$i$][$j$]))

6: end for

7: end for

8:end function

##  3 Methodology

The implementation was validated using the HIL simulation strategy, as
explained in (17) and illustrated in Figure 2. The tested variables are,
execution time for the FFM-$1$ for the hidden layer as seen in Figure 1
defined as $t_{\text{FFM-}1}$, execution time for the FFM-$2$, feedforward for
the output layer of neurons,$t_{\text{FFM-}2}$, error module $t_{\text{EM}}$,
backpropagation of the output neurons layer, $t_{\text{BPM-}1}$, and the
backpropagation of the hidden neurons layer, $t_{\text{BPM-}2}$.

A parameter that was also analyzed is the memory occupation, regarding both
memories of the ATMega-$2560$ $\mu$C used in this paper, FLASH or program
memory and SRAM or work memory.

As previously mentioned the modules were implemented in the C program language
for AVR $\mu$Cs using the avr-gcc version 5.4.0, inside the Atmel Studio 7
development environment, an Integrated Development Environment (IDE) made
available by Microchip. After compilation and binary code generation the
solution was embedded into an Atmega-$2560$. This $\mu$C has an 8-bit GPP
integrated with 256KBytes of FLASH program memory and 8KBytes of SRAM work
memory, its maximum processing speed is 1 MIPS/MHz.

The Atmega-$2560$ is associated to an Arduino Mega v2.0 development kit, the
Arduino Mega is a development kit that provides a breakout board for all the
ATmega-$2560$ pins and some other components required for the $\mu$C to
function properly. A great feature of this development kit is the onboard
Universal Serial Bus (USB) programmer that enables the developer to simply
connect a USB port to a computer and test various implementations easily on
the $\mu$C.

This work is further validated using two cases. First, we train the MLP-BP to
behave as an XOR operation as the simplest case possible to train an MLP and
evaluate its ability to learn a nonlinear relationship between two inputs.
Secondly, we train the network to aid a car-like virtual robot in avoiding
obstacles in a virtual map using Matlab and 3 cases of increasing ANN
architecture complexity. The assembly, and analysis of these two validation
cases are presented in the following subsections.

###  3.1 Hardware in the Loop Simulation

The tests were executed with the $\mu$C running at a clock of $16$MHz. The
results are obtained by setting the level of a digital pin of the
ATMega-$2560$ to HIGH, executing one of the modules and setting the same
digital pin logical value to LOW and measuring the time of logic HIGH on an
oscilloscope for this digital pin. This can be easily seen on Figure 2 and a
picture of the HIL assembly is shown in Figure 3. In Figures 5,6 we present
curved plots of the results described into 5 where we performed curve-fitting
on the measured points with Polynomial Regression. Figure 4 shows a closer
look on the oscilloscope measurements, taking in regard all the modules being
measured by their duration of execution for the XOR validation case described
below.

Figure 2: Hardware In the Loop assembly scheme in block diagram. Figure 3:
Hardware In the Loop assembly on the test bench. Figure 4: Hardware In the
Loop measurements of the embedded XOR operation using an oscilloscope.

The calculation of the MSE during training was also embedded into the $\mu$C
implementation and they’re transmitted through Universal Serial Synchronous
Asynchronous Receiver Transmitter (USART) protocol to a computer. The
calculation of the MSE is defined as

$MSE(n)=\frac{1}{2N}\text{trace}\left(\mathbf{E}(n)^{T}\mathbf{E}(n)\right)$
(15)

where $\text{trace}(\cdot)$ is the implementation seen in Algorithm 5.

###  3.2 XOR Operation

A validation of the real-time embedded training using the $\text{BPM}-k$
module was devised for a XOR operation, as described on Table 1, the most
basic MLP validation case. This test was performed with a training and
classification phases, both running in the $\mu$C, considering a configuration
as seen in Figure 1. The test was executed on batch mode with $\mathbb{N}=4$,
two layers of neurons ($L=2$), two input signals ($P=H^{0}=2$), a varying
amount of neurons in the hidden neurons layer ($H^{1}$) as seen in 5 and a
single neuron in the output layer ($H^{2}=1$). It is important to notice that
the strategy here presented can be assembled with various different
configurations just modifying the $P,H^{k}$ and $M$ parameters, being the
$\mu$Cs internal memories the limiting factor for the ANN architecture size.

Input A | Input B | Result
---|---|---
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0
Table 1: Truth table for the XOR operation

###  3.3 Virtual Car-Like Robot

This work also tested a MLP-BP model to control a virtual car-like robot from
the _iRobot_ matlab toolbox, provided by the United States Naval Academy
(USNA), (18). This toolbox provides a virtual environment and an interface to
test control algorithms on a deferentially steered robot on various maps with
different obstacles and different combinations of distance or proximity
sensors.

As previously stated, this virtual environment provides an interface to
control a deferentially steered virtual robot. This robot is controlled by
changing the angular speed in $rad/s$ of the two wheels, Right Wheel (RW) and
Left Wheel (LW). Also this work used three proximity sensors with virtual 3
meters range to provide input to the MLP. The sensors are Front-Sensor (FS),
Left-Sensor (LS) and Right-Sensor (RS).

We tested the MLP model with three different datasets, increasing the
hyperparameters to evaluate the behavior of the robot as we increased the
network architecture’s complexity. The cases are comprised of three tables
with five columns each, as seen in Table 2. The first case is very simple with
only eight conditions provided to train the network, which means the network
must be able to devise a knowledge representation on how to behave with cases
not previously trained from these simple constraints.

Condition | FS (m) | RS (m) | LS (m) | LW (rad/s) | RW (rad/s)
---|---|---|---|---|---
1 | 0.00 | 0.00 | 0.00 | 0.50 | -0.50
2 | 0.00 | 0.00 | 1.00 | -0.50 | 0.50
3 | 0.00 | 1.00 | 0.00 | 0.50 | -0.50
4 | 0.00 | 1.00 | 1.00 | 0.50 | -0.50
5 | 1.00 | 0.00 | 0.00 | 0.50 | 0.50
6 | 1.00 | 0.00 | 1.00 | 0.50 | 0.50
7 | 1.00 | 1.00 | 0.00 | 0.50 | 0.50
8 | 1.00 | 1.00 | 1.00 | 0.50 | 0.50
Table 2: Training dataset for the first and simplest case. With $H^{0}=3$,
$H^{1}=5$ and $H^{2}=2$.

The second case has a greater complexity with 18 conditions, as seen in Table
3. Also, as mentioned in Table 3 this case required the same amount of neurons
in the hidden layer, meaning that the first architecture could still be used
for a more complex case.

Condition | FS (m) | RS (m) | LS (m) | LW (rad/s) | RW (rad/s)
---|---|---|---|---|---
1 | 0.00 | 0.00 | 0.00 | -0.20 | 0.20
2 | 1.00 | 0.00 | 0.00 | -0.20 | 0.20
3 | 2.00 | 0.00 | 1.00 | -0.20 | 0.20
4 | 0.00 | 1.00 | 1.00 | 0.10 | 0.10
5 | 1.00 | 1.00 | 2.00 | 0.20 | -0.10
6 | 2.00 | 1.00 | 2.00 | 0.20 | -0.10
7 | 0.00 | 2.00 | 0.00 | 0.50 | 0.50
8 | 1.00 | 2.00 | 0.00 | 0.50 | 0.50
9 | 2.00 | 2.00 | 1.00 | 0.50 | 0.50
10 | 0.00 | 0.00 | 1.00 | 0.20 | 0.20
11 | 1.00 | 0.00 | 2.00 | 0.20 | -0.20
12 | 2.00 | 0.00 | 2.00 | 0.20 | -0.20
13 | 0.00 | 1.00 | 0.00 | 0.10 | 0.10
14 | 1.00 | 1.00 | 0.00 | 0.10 | 0.10
15 | 2.00 | 1.00 | 1.00 | -0.10 | 0.10
16 | 0.00 | 2.00 | 10.00 | 0.50 | 0.50
17 | 1.00 | 2.00 | 2.00 | 0.50 | 0.50
18 | 2.00 | 2.00 | 2.00 | 0.50 | 0.50
Table 3: Training dataset for the second case. With $H^{0}=3$, $H^{1}=5$ and
$H^{2}=2$.

The third and most complex case with 27 conditions to train the MLP-BP. This
dataset required a bigger architecture than the previous datasets, with double
the amount of neurons in the hidden layer ($H^{1}=10$)

Condition | FS (m) | RS (m) | LS (m) | LW (rad/s) | RW (rad/s)
---|---|---|---|---|---
1 | 0.50 | 0.50 | 0.50 | 0.30 | 0.30
2 | 0.50 | 0.50 | 1.00 | 0.20 | -0.20
3 | 0.50 | 0.50 | 2.50 | 0.20 | -0.20
4 | 0.50 | 1.00 | 0.50 | 0.30 | 0.30
5 | 0.50 | 1.00 | 1.00 | 0.20 | -0.20
6 | 0.50 | 1.00 | 2.50 | 0.20 | -0.20
7 | 0.50 | 2.50 | 0.50 | 0.30 | 0.30
8 | 0.50 | 2.50 | 1.00 | 0.30 | 0.30
9 | 0.50 | 2.50 | 2.50 | 0.30 | 0.30
10 | 1.00 | 0.50 | 0.50 | -0.20 | 0.20
11 | 1.00 | 0.50 | 2.50 | 0.20 | -0.20
12 | 1.00 | 1.00 | 0.50 | -0.20 | 0.20
13 | 0.50 | 1.00 | 0.50 | 0.30 | -0.30
14 | 1.00 | 1.00 | 1.00 | 0.30 | 0.30
15 | 1.00 | 1.00 | 2.50 | 0.20 | -0.20
16 | 1.00 | 2.50 | 0.50 | -0.20 | 0.20
17 | 1.00 | 2.50 | 1.00 | 0.30 | 0.30
18 | 1.00 | 2.50 | 2.50 | 0.20 | -0.20
19 | 2.50 | 0.50 | 0.50 | -0.20 | 0.20
20 | 2.50 | 0.50 | 1.00 | -0.20 | 0.20
21 | 2.50 | 0.50 | 2.50 | -0.20 | 0.20
22 | 2.50 | 1.00 | 0.50 | -0.20 | 0.20
23 | 2.50 | 1.00 | 1.00 | -0.20 | 0.20
24 | 2.50 | 1.00 | 2.50 | 0.20 | -0.20
25 | 2.50 | 2.50 | 0.50 | -0.20 | 0.20
26 | 2.50 | 2.50 | 1.00 | -0.20 | 0.20
27 | 2.50 | 2.50 | 2.50 | 0.30 | 0.30
Table 4: Training dataset for the third and most complex case. With $H^{0}=3$,
$H^{1}=10$ e $H^{2}=2$.

##  4 Results

###  4.1 XOR Operation

The binary code for the XOR operation, that is generated from this
implementation as seen in Figure 1, resulted in $6.672$ KBytes of program
memory occupation (equivalent to $2.6\%$), a pretty compact solution if
compared to the maximum program memory available for the ATMega-$2560$ and
also comparing to the $5.904$KBytes presented in (8) for and MLP
implementation without the BP training, considering that these $2.6\%$ already
include the training algorithm.

The information presented at Table 5 show that the values obtained up to
$H^{1}=38$ neurons in the hidden layer. The $H^{1}$ parameter is limited by
the available memory in the $\mu$C used, ATMega-$2560$. However, this value is
quite reasonable for most real-time applications in robotics and industrial
automation. Another noticeable result is that the processing times are also
reasonable. Analyzing the network without the training time results (EM,
BPM-$1$ and BPM-$2$) we can see that the iteration for a batch mode of
$\mathbb{N}=4$ samples takes $42.91\text{ms}$ for the worst case, $H^{1}=38$.
If you analyze the duration of each iteration including the network being
trained on the online mode it takes $69.88\text{ms}$, again in the worst case
of $H^{1}=38$. This shows that the implementation here presented is indeed
suitable for commercial applications in fields like industrial automation,
robotics, automotive industry, and others.

An important result of these tests is the behavior of these fitted curves in
Figures 5 and 6. The processing time grows linearly with the number of neurons
in the hidden layer ($H^{1}$). This result is quite significant since you can
estimate if a certain $\mu$C can be used with this implementation and also if
the network architecture that was chosen will fit or not in the $\mu$C. This
result can be used as a reference by other groups that refute the usage of
MLP-BP applications on $\mu$Cs.

$H^{1}$ | $t_{\text{FFM-}1}\,(\text{ms})$ | $t_{\text{FFM-}2}\,(\text{ms})$ | $t_{\text{EM}}\,(\text{ms})$ | $t_{\text{BPM-}1}\,(\text{ms})$ | $t_{\text{BPM-}2}\,(\text{ms})$
---|---|---|---|---|---
$2$ | $0\text{.}59$ | $0\text{.}31$ | $0\text{.}06$ | $0\text{.}46$ | $1\text{.}30$
$4$ | $4\text{.}28$ | $0\text{.}61$ | $0\text{.}06$ | $0\text{.}66$ | $2\text{.}23$
$6$ | $6\text{.}21$ | $0\text{.}77$ | $0\text{.}06$ | $0\text{.}88$ | $3\text{.}22$
$8$ | $8\text{.}11$ | $1\text{.}00$ | $0\text{.}06$ | $1\text{.}11$ | $4\text{.}11$
$10$ | $10\text{.}50$ | $1\text{.}82$ | $0\text{.}06$ | $1\text{.}70$ | $6\text{.}14$
$12$ | $12\text{.}30$ | $2\text{.}02$ | $0\text{.}06$ | $1\text{.}91$ | $6\text{.}90$
$14$ | $14\text{.}50$ | $1\text{.}49$ | $0\text{.}06$ | $1\text{.}80$ | $7\text{.}06$
$16$ | $16\text{.}30$ | $1\text{.}72$ | $0\text{.}06$ | $2\text{.}03$ | $8\text{.}02$
$18$ | $18\text{.}60$ | $2\text{.}57$ | $0\text{.}06$ | $2\text{.}65$ | $10\text{.}60$
$20$ | $20\text{.}70$ | $2\text{.}71$ | $0\text{.}06$ | $2\text{.}47$ | $11\text{.}20$
$22$ | $22\text{.}60$ | $2\text{.}95$ | $0\text{.}06$ | $3\text{.}07$ | $12\text{.}40$
$24$ | $25\text{.}20$ | $3\text{.}15$ | $0\text{.}06$ | $3\text{.}36$ | $13\text{.}60$
$26$ | $27\text{.}30$ | $3\text{.}31$ | $0\text{.}06$ | $3\text{.}71$ | $14\text{.}70$
$28$ | $29\text{.}30$ | $3\text{.}51$ | $0\text{.}06$ | $3\text{.}95$ | $16\text{.}50$
$30$ | $30\text{.}90$ | $3\text{.}67$ | $0\text{.}06$ | $4\text{.}03$ | $16\text{.}20$
$32$ | $32\text{.}90$ | $3\text{.}76$ | $0\text{.}06$ | $3\text{.}83$ | $15\text{.}80$
$34$ | $34\text{.}60$ | $3\text{.}36$ | $0\text{.}06$ | $4\text{.}05$ | $16\text{.}70$
$36$ | $36\text{.}50$ | $4\text{.}22$ | $0\text{.}06$ | $4\text{.}82$ | $19\text{.}40$
$38$ | $38\text{.}50$ | $4\text{.}41$ | $0\text{.}06$ | $5\text{.}17$ | $21\text{.}80$
Table 5: Duration of execution for each module of the implementation of the
MLP-BP with $P=H^{0}=2$, $M=H^{2}=1$ and sigmoid activation function.

Also we compared the MSE curve when varying the number of neurons in the
hidden layer ($H^{1}$), as shown in Figure 7. This shows that for 2 and 20
iterations the MSE was really close to zero, and that with 38 neurons, 80
iterations were needed. According to Table 5 it took approximately 8.28
seconds to fully train the XOR case with 38 neurons.

Figure 5: a) Execution time of $\text{FFM}-1$ by number of neurons in the
hidden layer, $H^{1}$. b) Execution time of $\text{FFM}-2$ by the number of
neurons in the hidden layer, $H^{1}$.

Figure 6: a) Execution time of $\text{BPM}-1$ by the number of neurons in the
hidden layer, $H^{1}$. b) Execution time of $\text{BPM}-2$ by the number of
neurons in the hidden layer, $H^{1}$. Figure 7: Mean Squared Error curve
fitting comparison with $H^{1}=\\{2,20,38\\}$ neurons in the hidden layer.

###  4.2 Virtual Car-like Robot

The first validation test-case showed small MSEs, close to $1\%$, with the
architecture described in the methodology section, three inputs and two
outputs with only five neurons in the hidden layer, ($H^{1}=$). Since it was
trained with a maximum distance of 1.0m, the robot shows a great behavior
close to obstacles, but on big empty spaces with greater than 1.0m distances
between obstacles the robot drifts and spins around the same spot until the
test is restarted. This showed us that this training dataset was too simple
and required more complex data. The test results for this dataset are shown in
Figure 8.

Figure 8: Virtual map with the resulting trajectory of the virtual car-like
robot for the $1^{st}$ training dataset.

The second dataset test showed much better results, with the virtual robot
being able to react quickly to farther obstacles and also correcting its
trajectory faster. The robot was able to run along the map borders smoothly
and keep a safe distance between parallel obstacles on the center of the map.
However, the virtual robot still collided with the obstacles and sometimes it
would collide and drag it self along the borders of bigger obstacles, as shown
in Figure 9.

Figure 9: Virtual map with the resulting trajectory of the virtual car-like
robot for the $2^{nd}$ training dataset.

The dataset for the third validation case resulted with a higher MSE of
$2.4\%$. The car-like robot was faster than the previous two tests and was
able to perform a fast reaction to abrupt changes in proximity to obstacles,
as shown in Figure 10. However, this dataset training made the robot show a
behaviour that can be interpreted as overfitting, since sometimes it would
react too quickly and start to spin around itself after detecting some
obstacles ahead.

Figure 10: Virtual map with the resulting trajectory of the virtual car-like
robot for the $3^{rd}$ training dataset.

The overall results shows that the datasets had not enough data and this
required some more tests with even more virtual sensors. We included the angle
between the Front-Sensor (FS) and the virtual horizontal axis of the test map.
Also we performed training tests with two and three more hidden layers (L =
3,4) and also hundreds of hidden neurons and thousands of iterations, none of
which improved the results, actually preventing the Neural Network from
reaching training error convergence lower than $20\%$.

The generated binary code from the source in C for the best dataset ($3^{rd}$)
had $3.07$KB of memory size, which amounts to $1.2\%$ of the $256$KB of
program memory of the ATMega2560. This code size is quite compact compared to
a similar model implementation seen in (8). The same variables and testing
criteria used for the XOR operation were used in this case, with 16Mhz of
clock frequency.

The timing results for the virtual car-like robot were expected, being smaller
than the XOR operation that has a simpler architecture with less inputs and
outputs ($H^{0}=1$ and $H^{2}=1$) and also a wide range for $H^{1}$, Table 5.
Also, as this implementation does not perform online real-time embedded
training, only the FFM-1, FFM-2 and FFM-3 modules were used, being
$\text{FFM-2}and\text{FFM-3}$ for the cases with more than one hidden layer.

The timing results for the first and second datasets were the same. This is
expected, since the only factor to influentiate the execution time is size of
the synaptic weight matrices $H^{1}$ and $H^{2}$ that depends only on the
amount of inputs, neurons and the amount of samples. Since this was not a
batch classification, but a single sample, online classification, the input
size remained as $1$ and unchanged throughout all the three tests.

The third case presented a fast timing result, but close to two times the
timing results for the first and second cases. This is expected and simply
reiterates what was shown in Figures 5 and 6, that the execution time grows
linearly with the hyperparameters or more specifically the amount of neurons
for this implementation proposal.

It is important to notice that the execution time results shown in Table 6
relate to what is found in the field’s literature, that more hidden layers do
not necessarily improves the training MSE and can actually make it worse, as
seen in (9). In the cases were we trained the robot with more than a single
hidden layer it’s ability to avoid obstacles did not improve and the best MSE
was slightly higher than $20\%$.

Datasets | $H^{1}$ | $t_{\text{FFM-}1}\,(\text{ms})$ | $t_{\text{FFM-}2}\,(\text{ms})$ | $t_{Total-\text{FFM-}k}$
---|---|---|---|---
1 | 5 | $1.28$ | $0.52$ | $1.80$
2 | 5 | $1.28$ | $0.52$ | $1.80$
3 | 10 | $2.63$ | $0.88$ | $3.51$
Table 6: Execution times measured with HIL for the implementation proposal in
the virtual car-like robot validation.

##  5 Comparison with the State-of-the-Art

The work McDanel et Al(9) shows two implementations of an MLP-BP with single
and dual hidden layers and their respective execution times for a
classification with the results shown in Table 7. In (6), the authors were
able to embed a full MNIST-10 classification model using CNNs under $2$KB of
SRAM being used, also the inference times were in the order of 640 ms per
input sample.

Reference | Model | Time (ms) | Memory (KB)
---|---|---|---
McDanel et Al(9) | MLP-1 | 17.35 | 14.73
McDanel et Al (9) | MLP-2 | 9.17 | 13.53
Gural & Murmann (6) | AvgPool2x2 + CNN3x3 + MaxPool + MLP | 684 | 8.46
Proposal | MLP-2 | 69.88* | 6.67
Table 7: ANN results for the state-of-the-art works.*Time of inference, not
taking the EM-k and BPM-k modules time into account.

It’s important to notice that not of the times presented in Table 7 take only
the inferencing time. The implementation for McDanel et Al (9) trained the
model offline using MatLab. For the Gural & Murmann (6) paper, the training
was executed offline as well on a Jupyter Notebook running Tensorflow-Keras
models and optimizations before porting the synaptic weights and kernels to
the $\mu$C.

It is possible to analyze this proposal, regarding how this system would
behave if it had to support the same hyperparameters that some of these state-
of-the-art applications have. The work presented by McDanel et Al(9) uses an
MLP ANN with a single layer with 100 artificial neurons. This same work also
presents another implementation with a two-layer MLP with 200 artificial
neurons. Analyzing the $t_{\text{FFM-}1},t_{\text{FFM-}2},t_{\text{BPM-}1}$
and $t_{\text{BPM-}2}$ fitted curves from Table 5 we obtain four predictive
equations that define how much time is required to process this MLP
implementation.

Equation 16 shows us again that this works proposal has a linear relationship
between inference time and hyperparameters, especifically artificial neurons.
Evaluating this Equation 16 with a number of 100 neurons it is observed
$1.18\text{s}$ of feedfowarding time for the first layer.

$t_{\text{FFM-}1}\left(H^{1}\right)=11.6\times H^{1}+20.52$ (16)

Taking in regard the same amount of neurons for the Equation 17 we get
$124.49\text{ms}$ of feedforwarding time for the second layer. This amount to
$1.30\text{s}$ of total inferencing time with 100 neurons.

$t_{\text{FFM-}2}\left(H^{2}\right)=1.22\times H^{2}+2.49$ (17)

If the embedded training is to be also considered with this amount of neurons,
the time duration for this process increases to $1.44\text{s}$, by evaluating
the Equation 18.

$t_{\text{BPM-}1}\left(H^{2}\right)=1.41\times H^{2}+2.72$ (18)

Also evaluating the Equation 19 for the second layer, considering two hidden
layers in training the time duration increases to $2.06\text{s}$.

$t_{\text{BPM-}2}\left(H^{1}\right)=6.03\times H^{1}+10.94$ (19)

This analysis shows that the modular implementation of a MLP here presented
performs on compatible training and inferecing times.

##  6 Conclusions

This work presents an implementation proposal of an MLP artificial neural
network with embedded BP training for an 8-bit $\mu$C. Results and
implementation details were presented for this proposal for an ATMega-$2560$
$\mu$Cs. Also, the validation results of the embedding of this proposal were
presented using a HIL simulation strategy. Finally, the results show that the
execution times and memory occupation of the implementation were compatible
with application requirements seen in the industry, seen that these
requirements fall under hundreds of milliseconds.

## References

  * (1) IEEE standard for binary floating-point arithmetic.  Institute of Electrical and Electronics Engineers, New York (1985).  Note: Standard 754–1985
  * (2) Cotton, N.J., Wilamowski, B.M.: Compensation of nonlinearities using neural networks implemented on inexpensive microcontrollers.  IEEE Transactions on Industrial Electronics 58(3), 733–740 (2011).  DOI 10.1109/TIE.2010.2098377
  * (3) Cotton, N.J., Wilamowski, B.M., Dundar, G.: A neural network implementation on an inexpensive eight bit microcontroller pp. 109–114 (2008).  DOI 10.1109/INES.2008.4481278
  * (4) Farooq, U., Amar, M., Hasan, K.M., Akhtar, M.K., Asad, M.U., Iqbal, A.: A low cost microcontroller implementation of neural network based hurdle avoidance controller for a car-like robot.  In: 2010 The 2nd International Conference on Computer and Automation Engineering (ICCAE), vol. 1, pp. 592–597 (2010).  DOI 10.1109/ICCAE.2010.5451340
  * (5) Fernandes, M.A.C.: The matrix implementation of the two-layer multilayer perceptron (mlp) neural networks.  https://bit.ly/35oQSuX (2012)
  * (6) Gural, A., Murmann, B.: Memory-optimal direct convolutions for maximizing classification accuracy in embedded applications.  In: K. Chaudhuri, R. Salakhutdinov (eds.) Proceedings of the 36th International Conference on Machine Learning, _Proceedings of Machine Learning Research_ , vol. 97, pp. 2515–2524. PMLR, Long Beach, California, USA (2019).  URL http://proceedings.mlr.press/v97/gural19a.html
  * (7) Haykin, S.: Neural Networks: A Comprehensive Foundation, 2nd edn.  Prentice Hall PTR, Upper Saddle River, NJ, USA (1998)
  * (8) Mancilla-David, F., Riganti-Fulginei, F., Laudani, A., Salvini, A.: A neural network-based low-cost solar irradiance sensor.  IEEE Transactions on Instrumentation and Measurement 63(3), 583–591 (2014).  DOI 10.1109/TIM.2013.2282005
  * (9) McDanel, B., Teerapittayanon, S., Kung, H.T.: Embedded binarized neural networks.  CoRR abs/1709.02260 (2017).  URL http://arxiv.org/abs/1709.02260
  * (10) Misra, J., Saha, I.: Artificial neural networks in hardware: A survey of two decades of progress.  Neurocomputing 74(1-3), 239 – 255 (2010).  Artificial Brains
  * (11) Noronha, D., Fernandes, M.A.C.: Implementação em fpga de máquina de vetores de suporte (svm) para classificação e regressõ.  In: XIII Encontro Nacional de Inteligência Artificial e Computacional - ENIAC 2016. Recife, PE (2016)
  * (12) Ortega-Zamorano, F., Jerez, J.M., noz, D.U.M., Luque-Baena, R.M., Franco, L.: Efficient implementation of the backpropagation algorithm in fpgas and microcontrollers.  IEEE Transactions on Neural Networks and Learning Systems 27(9), 1840–1850 (2016).  DOI 10.1109/TNNLS.2015.2460991
  * (13) Oyamada, M.S., Zschornack, F., Wagner, F.R.: Applying neural networks to performance estimation of embedded software.  Journal of Systems Architecture 54(1-2), 224 – 240 (2008)
  * (14) Saad Saoud, L., Khellaf, A.: A neural network based on an inexpensive eight-bit microcontroller.  Neural Computing and Applications 20(3), 329–334 (2011)
  * (15) L. da Silva, M.T., Fernandes, M.A.C.: Proposta de arquitetura em hardware para fpga da técnica q-learning de aprendizagem por reforço.  In: XIII Encontro Nacional de Inteligência Artificial e Computacional - ENIAC 2016. Recife, PE (2016)
  * (16) de Souza, A.C., Fernandes, M.A.: Parallel fixed point implementation of a radial basis function network in an fpga.  Sensors 14(10), 18,223–18,243 (2014)
  * (17) de Souza, I., Natan, S., Teles, R., Fernandes, M.: Platform for real-time simulation of dynamic systems and hardware-in-the-loop for control algorithms.  Sensors 14(10), 19,176–19,199 (2014)
  * (18) United States Naval Academy USNA: Matlab Toolbox for the iRobot Create V2.0.  https://www.mathworks.com/matlabcentral/fileexchange/32698-matlab-toolbox-for-the-irobot-create-v2-0 (2011)
  * (19) Ursuţiu, D., Nascov, V., Samoilă, C., Moga, M.: Microcontroller technologies in low power applications.  In: 2012 15th International Conference on Interactive Collaborative Learning (ICL), pp. 1–5 (2012).  DOI 10.1109/ICL.2012.6402096
  * (20) Zhang, L., Wang, Z.F.: Design of embedded control system based on arm9 microcontroller.  In: 2010 International Conference on Electrical and Control Engineering, pp. 3579–3582 (2010).  DOI 10.1109/iCECE.2010.873


# GausSetExpander: A Simple Approach for Entity Set Expansion

Aïssatou Diallo† and Johannes Fürnkranz‡
†Department of Computer Science, Technische Universität Darmstadt
‡Computational Data Analytics, FAW, Johannes Kepler University Linz, Linz,
Austria
<EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

Entity Set Expansion is an important NLP task that aims at expanding a small
set of entities into a larger one with items from a large pool of candidates.
In this paper, we propose GausSetExpander, an unsupervised approach based on
optimal transport techniques. We propose to re-frame the problem as choosing
the entity that best completes the seed set. For this, we interpret a set as
an elliptical distribution with a centroid which represents the mean and a
spread that is represented by the scale parameter. The best entity is the one
that increases the spread of the set the least. We demonstrate the validity of
our approach by comparing to state-of-the art approaches.

##  1 Introduction

The Entity Set Expansion (ESE) task aims at expanding a small seed set e.g
{Paris, Berlin} to a larger set of entities that belong to the same semantic
class, in this example Capitals. Loosely speaking, the goal is to find all
other entities in a given corpus that complete the original set of seed
entities. From a theoretical point of view, the ESE task can be seen as a
problem of generalization from few examples. The steps that are necessary to
successfully solve this problem are: (1) identifying the semantic class from
the given seed set; (2) identifying similar examples from a large pool of
items that fit the semantic class. This task is useful to several downstream
applications such as question answering Wang et al. (2008), taxonomy
construction Shen et al. (2018), relation extraction Lang and Henderson (2013)
and query suggestion Cao et al. (2008).

In this paper, we propose an approach to tackle the ESE task based on
pretrained embedding models and optimal transport techniques. It has been
vastly shown that pretrained embedding models contain semantic, syntactic and
knowledge background that could facilitate transfer learning tasks.

One of the major challenges of ESE is the limited (or lack thereof) of
supervision. In fact, generally the set seed is too small for fine-tuning and
sometimes, the ground truth semantic class is an open set. From the
literature, we can identify two main ways of solving the ESE task: a pattern-
based approach and a distributional approach. The first has as an objective
mining revealing textual patterns in the corpus that signal the semantic class
and extracting the correct entity from this patterns. On the other hand, the
distributional approach relies on the assumption that similar words appear in
similar contexts. These methods operate by representing each term in the
vocabulary as an embedding vector that summarizes all the contexts the term
appears within a large corpus, and then look for terms with vectors that are
similar to those of the seed entity. One of the main critiques to these
approaches is that they consider all occurrences of a term in the corpus when
calculating its representation, including many contexts that are irrelevant or
non-informative to the concept which cause noise in the corpus.

We propose an algorithm that is more similar to the distributional approach,
although our algorithm has some notable differences. _GausSetExpander_ ,
proceeds in an iterative manner across all terms in a vocabulary V, extracted
from a corpus D. Given an initial set seed $S_{0}$, and two terms embedded
with a pretrained embedding model, we aim at finding the term that completes
better the original set seed $S_{0}$. For doing this, we simply produce two
different expanded sets from the simple concatenation of the previously two
random terms to the seed set and we evaluate the better expansion. The
evaluation of the new obtained sets relies on techniques related to optimal
transport, elliptical embeddings and sets clustering, which are concepts this
thesis is treating. In a nutshell, we leverage the fact that one of the most
common statistics of a set $S$ is its centroid $c(S)\in\mathbb{R}^{d}$ ,
represented as:

$c(S)=\frac{1}{|S|}\sum_{i\in S}x_{i}$ (1)

This implies that, it is possible to approximate a set of vectors to its
centroid. Another key element of our approach comes from the literature of
Gaussian embeddings, which has demonstrated to provide a better and richer
representation for items in the latent space. In fact, a Gaussian embedding is
characterized by two parameters, the mean vector which represents the location
in the latent space and the covariance matrix, which encodes the dispersion
around the location vector, that is to say the uncertainty of the
representation.

We hypothesise that given an original seed set and two candidate items to
expand it, the better entity is the one that causes the less increase in the
dispersion of the set. This hypothesis is the key element of GausSetExpander.
Additionally, ESE is a challenging task for the lack of available labels. For
this reason, the pretrained embedding is a key element, because at each
iteration we produce a weak label based on the cosine similarity between the
centroid of the seed set and each candidate term. Finally, we rank the scores
in order to identify candidates term from the vocabulary to generated the
expanded set. To summarize, in this study we propose an iterative approach
based on Gaussian representation for the ESE task to expand a seed set. We
conduct experiments to verify our hypotheses and show the effectiveness of
GausSetExpander.

##  2 Problem Formulation

#### Terminology

In this section, we formally introduce the concepts necessary for this study
as well the Entity Set Expansion problem. An entity is a string, that can be
either a word or a phrase, that corresponds to a real-world entity in
designated category. This category, is better defined as a semantic class
which is a set of entities that share a common characteristic, for example
fruits or animals. An entity set, is a set of terms that refers to the same
real-world entity. More specifically, UK and United Kingdom refers to the same
entity, hence are an entity synset. It is worth mentioning that an entity
synset can be a singleton. Finally, a vocabulary is a list of terms that is
derived from a given corpus.

#### Problem Formulation

Given a text corpus $D$, a vocabulary $V$ extracted from $D$, a seed set of
size $n$ (usually small) of terms $S_{0}=[e_{1},e_{2},...e_{n}]$ from the same
semantic class $C$, the ESE task aims at expanding $S_{0}$ with terms from the
vocabulary $V$ from the same semantic class $C$. In practice, the goal is to
rank all available entities and said ranking must have the terms that best
expand $S_{0}$ at the top of the ranking.

##  3 Approach

In this section, we first lay down the notation as well as the mathematical
background used for our hypothesis. Then we describe our hypothesis and the
algorithm we proposed: _GausSetExpander_.

###  3.1 Notation

$\mathcal{S}^{d}_{+}$ is the set of all positive definite matrices. In the
scope of this work, we only focus on Gaussian distributions which belong to
the family of parameterized probability distributions
$z_{h,\mathbf{a},\mathbf{A}}$ having a location vector
$\mathbf{a}\in\mathbb{R}^{d}$ which represents the shift of the distribution,
a scale parameter $\mathbf{A}\in\mathcal{S}^{d}_{+}$, that represents the
statistical dispersion of the distribution, and a characteristic generator
function $h$. This is the same hypothesis that have been used throughout the
thesis. Specifically, for Gaussian distributions, the scale parameter
coincides with the covariance matrix
$var(z_{h,\mathbf{a},\mathbf{A}})=\mathbf{A}$. From now on, we denote Gaussian
distributions (or embeddings) as
$z_{(h,\mathbf{a},\mathbf{A})}=\mathcal{N}(\mathbf{a},\mathbf{A})$.

Finally, when stated $\operatorname{Tr}$, we indicate the trace operator, that
is the sum of the diagonal elements of a matrix.

###  3.2 Mathematical Background

We need to explicitly describe few mathematical concepts useful the
understanding of our hypothesis. First, as briefly mention in Section 1, one
key element in our approach is the notion of centroid of a set from eq. (1).
In fact an (aggregation) function that takes as input a set must respect the
property of permutation to the order of objects in the set. Good candidate
functions are the sum or the average, hence the centroid is a good
representation a given set. Then, we need to go from the point-vector
representation of an item to a distributional representation. We choose to
focus on Gaussian distributions, particularly diagonal Gaussian distributions.
For doing this we propose to use a set encoder, that takes as input a vector,
mainly the centroid of the set and outputs a location vector $\mu$ and the
diagonal of a covariance matrix $d_{\Sigma}$. These concepts have been fully
described in LABEL:sec:set_eloe_chap.

Finally, we need to describe the scoring function that takes as input two
Gaussian representation of sets and assess which one is the better
representation. As stated earlier, the best set is the one that have the
smallest dispersion. We propose to use the $\operatorname{Tr}$, trace operator
for scoring the sets. This is derived from the optimal transport theory, in
particular the Wasserstein distance which have been fully explained in
LABEL:para:wasserstein.

We recall the Wasserstein distance derived from the appropriate
simplifications, and relying on the squared Bures metric and squared Hellinger
metric:

$W^{2}_{2}(\alpha,\beta)=\|\mathbf{a}-\mathbf{b}\|^{2}+\|\sqrt{\mathbf{d_{A}}}-\sqrt{\mathbf{d_{B}}}\|^{2}$
(2)

##  4 GausSetExpander

In the following section, we present the proposed approach for the Entity Set
Expansion task. We propose an iterative approach that takes as input a small
seed set and two candidates term and outputs two scores that indicates the
better alternative. In a nutshell, our main hypothesis is that given two
candidate entity for expanding the seed set, the better hypothesis will "fit"
better the input set. We choose to represent this fit by considering the
dispersion that the addition of a new term will cause to an existent set. A
well suited mathematical notion for representing the dispersion around a
center is the covariance matrix of a Gaussian distribution. That is the first
key element of GausSetExpander. Algorithm 1 describes our approach.

Figure 1: Overview of the set encoder that takes as input a set of terms and
outputs a tuple of mean vector and a covariance matrix for the Gaussian
distribution.

#### Set Encoder

Given a seed set, the first step is to encode it as a tuple of location vector
and covariance matrix in order to have the the dispersion before adding the
candidate terms for the expansion. For this, we represent the element-wise
embedding function $\phi(.)$ as a deep neural network, as illustrated in
Figure fig. 1. This network takes as input a set, very similarly to the model
proposed in LABEL:sec:set_eloe_chap. We again choose to only focus on diagonal
covariance matrices for the sake of simplicity. A first deep encoder, namely a
2-layer MLP with Relu, $\phi_{\theta}(\cdot)$ maps these random inputs into
$d$-dimensional outputs. These are then aggregated to $\mu_{\theta}(\cdot)$
and fed to produce the variance $\Sigma_{\theta}(\cdot)$, a function which is
again represented with a deep forward network.

1

2

Input : corpus $D$, vocabulary $V$, set $S_{0}$

3

4for  _$t\leftarrow 0$ to $|D|$_ do

5 Get i, j, $c_{i}$, $c_{j}$ from $D$

6 Embed i and j to $\mathbf{e_{i}}\in\mathbb{R}^{d}$,
$\mathbf{e_{j}}\in\mathbb{R}^{d}$

7 Embed terms in $S_{0}$ to $[\mathbf{e_{0}},...,\mathbf{e_{n}}]$

8 Encode $S_{0}\leftarrow\mathcal{N}(\mu_{0},\Sigma_{0})$:
$c(S_{0})=\frac{1}{n}\sum_{i}e_{i}$ $\mu_{0}$= $\phi_{\mu}(c(S_{0}))$
$\Sigma_{0}$ = $e^{\frac{1}{2}\phi_{\Sigma}(c(S_{0}))}$

9 Append $\mathbf{i}$ and $\mathbf{j}$ to $S_{0}$:
$S_{t}^{{}^{\prime}}=[S_{0},e_{i}]$ and
$S_{t}^{{}^{\prime\prime}}=[S_{0},e_{j}]$

10 Compute cosine similarity:
$sim_{1}=\cos(c(S_{0}),c(c_{i}))$ and $sim_{2}=\cos(c(S_{0}),c(c_{j}))$

11 if  _$sim_{1}$ > $sim_{2}$_ then

12 $l=1$

13 else

14 $l=-1$

15 end if

16 Encode $S_{t}^{{}^{\prime}}$ and $S_{t}^{{}^{\prime\prime}}$:
$S_{t}^{{}^{\prime}}\leftarrow\mathcal{N}(\mu_{t}^{{}^{\prime}},\Sigma_{t}^{{}^{\prime}})$
$S_{t}^{{}^{\prime\prime}}\leftarrow\mathcal{N}(\mu_{t}^{{}^{\prime\prime}},\Sigma_{t}^{{}^{\prime\prime}})$

17 Compute the score:
$score(i|S_{0})=W((\mu_{0},\Sigma_{0}),(\mu_{i},\Sigma_{i}))$
$score(j|S_{0})=W((\mu_{0},\Sigma_{0}),(\mu_{j},\Sigma_{j}))$
$l(i,j|S_{0})=\max(0,s(i|S_{0})-s(j|S_{0}))$

18 end for

Algorithm 1 GausSetExpander

#### Scoring function

After describing the step to obtain the Gaussian representation of the sets,
we illustrate the scoring process. In practice, most of the proposed methods
for solving the ESE problem return a (top-k) ranking of the vocabulary rather
than a fixed set. Then the evaluation is done on the returned ranking.
Ideally, all terms that belongs to the semantic class identified by the seed
set should be ranked higher.

From the Wasserstein distance in eq. (2), we derive the scoring function for
two given expanded sets encoded as Gaussian distributions is:

$score(S_{i},S_{j})=W((\mu_{i},\Sigma_{i}),(\mu_{j},\Sigma_{j}))$ (3)

This scoring function can be interpreted as point-wise mutual information
between the the candidate item and the set to be expanded.

We stated earlier that GausSetExpander proceeds in stages. It first encodes
the seed set $S_{0}$ as a tuple of vectors $\mathbf{\mu}_{0}$ and
$\mathbf{\sigma}_{0}$. Then, it appends each candidate to the seed set $S_{0}$
to obtain two new sets $S^{\prime}$ and $S^{\prime\prime}$, which are
transformed in Gaussian distributions as well. It is worth mentioning, that
the weights of the set encoder shared are shared among candidates. Finally,
the scoring function proceeds as follows:

$\displaystyle
score(i|S_{0})=W((\mu_{0},\Sigma_{0}),((\mu^{\prime},\Sigma^{\prime})))$ (4)
$\displaystyle
score(j|S_{0})=W((\mu_{0},\Sigma_{0}),((\mu^{\prime\prime},\Sigma^{\prime\prime})))$
(5)

where $(\mu_{0},\Sigma_{0})$ are the parameters of the Gaussian encoding of
$S_{0}$. $(\mu^{\prime},\Sigma^{\prime})$ and
$(\mu^{\prime\prime},\Sigma^{\prime\prime})$ are the parameters for
$[S_{0},i]$ and $[S_{0},j]$. $[]$ indicates the concatenation.

(a) The expanded set $S^{\prime}$ has a small increase in the dispersion after
adding the entity $i$ to the seed set $s_{0}$.

(b) The expanded set $S^{\prime\prime}$ has a greater increase in the
dispersion after adding the entity $j$ to the seed set $s_{0}$.

Figure 2: Illustration of the hypothesis under GausSetExpander. Given two
candidate entity for the seed set $S_{0}$, the better candidate is the one
that will induce the least increase in the dispersion of the generated set.

#### Loss function

For learning the score, we utilize the large-margin classification loss:

$l(i,j|S_{0})=\max(0,s(i|S_{0})-s(j|S_{0})+\Delta(i,j))$ (6)

Loosely speaking, this loss function is to ensure that
$s(i|S_{0}))>s(j|S_{0})+\Delta(i,j)$ whenever $i$ should be preferred for
expanding $S_{0}$ over $j$.

#### Weak supervision

Per definition, the ESE tasks is challenging for the lack of proper
supervision under the form of ground truth labels. Several works in the area
rely on pre-trained language models or pre-trained embedding models to deliver
the semantic, syntactic and background knowledge to provide weak labels. We
proceed in the same manner, and use Glove Pennington et al. (2014) for
encoding the terms extracted from the corpus. Moreover, we assume that the
seed terms are part of vocabulary. In order to generate, weak labels for
training the scoring function we leverage the distributional hypothesis of the
language models. In fact, that hypothesis states that similar words appear in
similar contexts. For this reason, given two candidates terms $i$ and $j$, we
extract their context as well, $c_{i},$ and $c_{j}$ respectively. Then we use
the simple cosine similarity to induce a weak label $l$:

$l(S_{0},c_{i},c_{j})=\left\\{\begin{array}[]{ll}+1&\mbox{if
}R(c_{i}|S_{0})>R(c_{j}|S_{0})\\\ -1&\mbox{if
}R(c_{i}|S_{0})<R(c_{j}|S_{0})\end{array}\right.$ (7)

The function $R$ is defined as follows:

$R(c,S_{0})=\max_{x\in c_{i},s\in S_{0}}\cos(x,s_{i})$ (8)

1

Input : corpus $D$, vocabulary $V$, set $S_{0}$

2

3for  _$t\leftarrow 0$ to $|D|$_ do

4 Get i, j, $c_{i}$, $c_{j}$ from $D$

5 Embed i and j to $\mathbf{e_{i}}\in\mathbb{R}^{d}$,
$\mathbf{e_{j}}\in\mathbb{R}^{d}$

6 Embed terms in $S_{0}$ to $[\mathbf{e_{0}},...,\mathbf{e_{n}}]$

7 Encode $S_{0}$ as its centroid:
$c(S_{0})=\frac{1}{n}\sum_{i}e_{i}$ Append $\mathbf{i}$ and $\mathbf{j}$ to
$S_{0}$:
$S_{t}^{{}^{\prime}}=[S_{0},e_{i}]$ and
$S_{t}^{{}^{\prime\prime}}=[S_{0},e_{j}]$

8 Compute cosine similarity:
$sim_{1}=\cos(c(S_{0}),c(c_{i}))$ and $sim_{2}=\cos(c(S_{0}),c(c_{j}))$

9 if  _$sim_{1}$ > $sim_{2}$_ then

10 $l=1$

11 else

12 $l=-1$

13 end if

14 Encode $S_{t}^{{}^{\prime}}$ and $S_{t}^{{}^{\prime\prime}}$ as their
centroids:
$S_{t}^{{}^{\prime}}\leftarrow c(S_{t}^{{}^{\prime}})$
$S_{t}^{{}^{\prime}}\leftarrow c(S_{t}^{{}^{\prime\prime}})$

15 Compute the score:
$score(i|S_{0})=l^{2}(c(S_{0})-c(S_{t}^{{}^{\prime}}))$
$score(j|S_{0})=l^{2}(c(S_{0})-c(S_{t}^{{}^{\prime}}))$
$l(i,j|S_{0})=\max(0,s(i|S_{0})-s(j|S_{0}))$

16 end for

17

Algorithm 2 CentroidSetExpander

##  5 Experiments

In this section we describe our experimental setting as well as the main
results obtained.

#### Dataset

We used English Wikipedia as the corpus. Following, Kushilevitz et al. (2020),
we use for evaluation 7 datasets of closed sets. These sets are the are
National football league teams (NFL, size:32), Major league baseball teams
(MLB, size:30), US states (US, size:50), Countries (Cntrs, size:195), European
countries (Euro, size:44) Capital cities (Caps, size:195) and Presidents of
the USA (Pres, size:44) and one open class set: Music Genres (Genre).

Method | NFL | MLB | Pres | US | Cntrs | Euro | Caps | Music | Avg
---|---|---|---|---|---|---|---|---|---
SetExpander | .54 | .45 | .33 | .55 | .55 | .61 | .14 | .99 | .52
CB | .98 | .97 | .70 | .93 | .74 | .46 | .21 | .67 | .71
Cent-SetExp. | .89 | .67 | .10 | .70 | .64 | .46 | .19 | .62 | .54
GausSetExp. | .98 | .69 | .14 | .98 | .76 | .74 | .34 | .98 | .70
Table 1: Set expansion results. We report the MAP@k for different k. Results
are averaged over 3 random seed of cardinality 3.

#### Setup and Evaluation

We rely on 300-dimensional Glove for obtaining the pre-trained embedding.
Moreover, we fix the maximum number of terms to 200,000 most frequent terms.
Our approach has also a learning module, for which we need to define the
following hyperparameters $l_{r}=1e-3$ as the learning rate, batch size $512$,
$h=64$ as the hidden size. Following other works in the literature, we chose
the Mean Average Precision (MAP) at different positions k for evaluating our
approach:

$MAP@k=\frac{1}{|V|}\sum_{t\in V}AP(S_{exp},S_{gt})$ (9)

where $AP(S_{exp},S_{gt})$ is the average precision at position k given the
ranked expanded set $S_{exp}$ and the ground-truth set $S_{gt}$. The training
and the evaluation is done with random set seeds of cardinality 3 and the
results presented are averaged over random seeds. We follow the recommendation
of the authors of the datasets used for evaluation and fixed the size of the
expanded set to 200 for smaller sets and to 350 for bigger sets that have size
> 100\. The open set of music genre is evaluate with $\text{MAP}_{70}$.

#### Baseline methods

We compare our approach to the following corpus based ESE approaches:
SetExpander Mamou et al. (2018), a method based on entity ranking based on
multi-context entity similarity defined on multiple embeddings, Category
Builder Mamou et al. (2018). Both this approaches are distributional, which is
the category to which our method belongs to. For the sake of gaining a better
insight of our hypothesis, we add a natural comparison approach which consists
in our same architecture but the encoding of the sets remain the centroid
representation. This comparison will act as an ablation experiment which we
perform to assess the benefit or lack thereof of the Gaussian representation
of the sets. We call this last baseline, Centroid-SetExpander and we described
it in algorithm 2.

#### Results

We assess the set expansion performance by comparing our approach to the
baselines methods. Table 1 presents the quantitative evaluation of our model.
We can notice that GausSetExpander achieves comparable performance with
current state-of-the-art methods. This demonstrates the validity of our
hypothesis. When doing a fine grained analysis, we notice that GausSetExpander
performs particularly poorly in the semantic class corresponding to the
"Presidents". When investigating the results retrieved, we hypothesize that
our algorithm probably fails in recognising the acronyms. In fact, a typical
synset for the class "Presidents" will be "John_Fitzgerald_Kennedy,
John_F._Kennedy, John_F_Kennedy, John_Kennedy, Kennedy, JFK". We hypothesize
that probably a better encoding of the entities and tokens could resolve this
problem.

An emblematic example could be that, among the top retrieved entity for the
class "Presidents" we can find "Hillary" or "Barack" or even Presidents of
other nations which were not present among the ground-truths. This let us
think that the results might not be as bad as the numerical evaluation lead to
think. Table 2 showcases few examples of top ranked entities but rejected.

One reason for this phenomenon could be the fact that the weak label is
generated from a very noisy procedure. In fact, it is the result of the cosine
similarity between the centroid of the set seed and the contexts of the 2
candidates entities. We hypothesize that a better method for generating a weak
label than the naive cosine similarity could be beneficial. This leads to a a
second point that it is worth mentioning which is that, our algorithm is very
sensible to the amount of data. In fact, after a threshold which we
empirically estimated around 50,000 articles, with a vocabulary of around
500,000 terms, we notice that the labels become extremely noisy and the
overall performance degrades rapidly.

Finally, we compare GausSetExpander to CentroidSetExpander. We notice that the
performance of the latter is worse in all datasets, and it declines even
further for the semantic class "Presidents". This confirms that our initial
hypothesis of considering the Wasserstein Distance between the sets is
effective for the task of Entity Set Expansion.

Seed set | Top-k results
---|---
Presidents | [’mccain’, ’barack’, ’hillary’, ’gore’, ’fahmy’, ’letterman’]
Capitals | [’georgia’, ’ababa’, ’petersburg’, ’berliner’, ’sapienza’]
Countries | [’maldive’, ’federation’, ’duchy’, ’bissau’, ’herzegovina’]
MLB | [’milwaukee’, ’hammonds’, ’packers’, ’tigers’, ’cardinals’]
Euro | [”herzegovina’, ’yugoslavia’, ’slovak’, ’tirana’, ’uzbekistan’]
Table 2: Case study of entities retrieved but rejected for the least
performing semantic classes.

##  6 Related Work

#### Entity Set Expansion

Entity Set Expansion is a task that can be seen as a intermediate step form
many problems and applications such as question answering or literature
search. It was common for entity set expansion systems such as Google Sets
Tong and Dean (2008) and SEAL Wang et al. (2008) to submit a query made of
seed entities to a general-domain search engine and then extract new entities
from retrieved web pages. Web-based methods for set expansion Chen et al.
(2016) extract entities from documents retrieved by a search engine. The
documents are chosen with respect to the query obtained from seed entities.
However, this type of approaches demand an external search engine adapted to
seed-oriented data, which could be costly. In fact, such methods impose
significant run-time overhead and they make the assumption that top-ranked web
pages contain other entities of the set, which might not necessarily exact.

As a solution, more recent works propose to expand the seed set processing a
corpus offline without the need to prompt an online search engine. These
corpus-based set expansion methods can be categorized into two general
approaches: (1) entity ranking which calculates entity similarities and ranks
all entities Mamou et al. (2018); Pantel et al. (2009); Kushilevitz et al.
(2020), and (2) iterative bootstrapping whose goal is to bootstrap the seed
entity set by iteratively selecting context features and ranking new entities
Shen et al. (2017); Huang et al. (2020); Rong et al. (2016) with respect to
the original seed set. The approach proposed in this paper belongs to the
first category.

#### Pre-training

Early works in computer vision on ImageNet Russakovsky et al. (2015) have
shown the advantages of pretrained models Huang et al. (2017); He et al.
(2017). In Natural Language Processing, pretrained embeddings such as Glove
Pennington et al. (2014) or Word2Vec Mikolov et al. (2013) have also proven to
be highly effective in several tasks. In addition to the embeddings, the
pretrained language models are currently vastly used such as BERT Devlin et
al. (2019).

#### Set encoding

Machine learning on sets can be divided into different subgroups depending on
the nature of the input and output (e.g vector-to-set, set-to-set, set-to-
sequence). Our work falls under the category of vector-to-set such as Zhang et
al. (2020, 2019a). Notable works in vector-to-set literature are suited to
tasks such as object detection, taking as input a feature representation of an
images and producing set of coordinates for the bounding boxes. Loosely
related are also methods like Zhang et al. (2019b) that learn a permutation
matrix for sets of items. Once the permutation matrix is learned, it is
applied to the input set in order to turn the set into an (ordered) sequence.
Once again, our method differs because the output set is not ordered, hence
not a sequence.

#### Probabilistic Embeddings

The work of Vilnis and McCallum (2015) established a new trend in the
representation learning field by proposing to embed data points, in this case
words, as probability distributions in $\mathbb{R}^{d}$. Representing objects
in the latent space as probability distributions allows more flexibility in
the representation and even express multi-modality. In fact, point embeddings
can be considered as a special case of probabilistic embeddings, namely a
Dirac distribution, where the uncertainty is collapsed in a single point. In
the above-mentioned work Vilnis and McCallum (2015), the metric used is KL
divergence. However, this metric has a drawback: when variances of the
probabilistic embedding collapse, the measure does not coincide with the
Euclidean metric between point embeddings. Loosely speaking, the KL divergence
and the $\ell_{2}$ distance between two probability measures diverge to
infinity when the variances become too small. In addition, the KL divergence
does not behave well when the two compared distributions have little or no
overlap. It has been shown by Muzellec and Cuturi (2018) that the Wasserstein
metric is a better metric to compare probabilistic embeddings.

##  7 Conclusion

We introduce an iterative and distributional approach for the task of Entity
Set Expansion. Our method is based on encoding sets of vectors as Gaussian
distributions. These probabilistic representations are learned from the
centroid of the sets and are useful because they allow to represents the sets
as a tuple of location and dispersion. In fact, our main hypothesis states
that given to ncandidates entities for a set, the best candidate will be the
entity that will cause the least increase in the dispersion, represented as
the covariance matrix. Finally, we use a scoring function based on the
Wasserstein distance. The quantitative evaluation on benchmark datasets
demonstrate the effectiveness of our approach.

## Acknowledgments

This work has been supported by the German Research Foundation as part of the
Research Training Group Adaptive Preparation of Information from Heterogeneous
Sources (AIPHES) under grant No. GRK 1994/1.

## References

  * Cao et al. (2008) Huanhuan Cao, Daxin Jiang, Jian Pei, Qi He, Zhen Liao, Enhong Chen, and Hang Li. 2008.  Context-aware query suggestion by mining click-through and session data.  In _Proceedings of the 14th ACM SIGKDD international conference on Knowledge discovery and data mining_ , pages 875–883.
  * Chen et al. (2016) Zhe Chen, Michael Cafarella, and HV Jagadish. 2016.  Long-tail vocabulary dictionary extraction from the web.  In _Proceedings of the Ninth ACM international conference on Web search and data mining_ , pages 625–634.
  * Devlin et al. (2019) Jacob Devlin, Ming Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _NAACL HLT 2019 - 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies - Proceedings of the Conference_ , volume 1.
  * He et al. (2017) Kaiming He, Georgia Gkioxari, Piotr Dollár, and Ross Girshick. 2017.  Mask r-cnn.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2961–2969.
  * Huang et al. (2020) Jiaxin Huang, Yiqing Xie, Yu Meng, Jiaming Shen, Yunyi Zhang, and Jiawei Han. 2020\.  Guiding corpus-based set expansion by auxiliary sets generation and co-expansion.  In _Proceedings of The Web Conference 2020_ , pages 2188–2198.
  * Huang et al. (2017) Jonathan Huang, Vivek Rathod, Chen Sun, Menglong Zhu, Anoop Korattikara, Alireza Fathi, Ian Fischer, Zbigniew Wojna, Yang Song, Sergio Guadarrama, et al. 2017.  Speed/accuracy trade-offs for modern convolutional object detectors.  In _Proceedings of the IEEE conference on computer vision and pattern recognition_ , pages 7310–7311.
  * Kushilevitz et al. (2020) Guy Kushilevitz, Shaul Markovitch, and Yoav Goldberg. 2020.  A two-stage masked lm method for term set expansion.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 6829–6835.
  * Lang and Henderson (2013) Joel Lang and James Henderson. 2013.  Graph-based seed set expansion for relation extraction using random walk hitting times.  In _Proceedings of the 2013 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 772–776.
  * Mamou et al. (2018) Jonathan Mamou, Oren Pereg, Moshe Wasserblat, Alon Eirew, Yael Green, Shira Guskin, Peter Izsak, and Daniel Korat. 2018.  Term set expansion based nlp architect by intel ai lab.  _arXiv preprint arXiv:1808.08953_.
  * Mikolov et al. (2013) Tomas Mikolov, Kai Chen, Greg Corrado, and Je rey Dean. 2013.  Distributed Representations of Words and Phrases and their Compositionality. Nips (2013), 1–9. DOI: h p.  In _Dx. Doi. Org/10.1162/Jmlr_.
  * Muzellec and Cuturi (2018) B. Muzellec and M. Cuturi. 2018.  Generalizing point embeddings using the Wasserstein space of elliptical distributions.  In _Advances in Neural Information Processing System 31_ , pages 10258–10269.
  * Pantel et al. (2009) Patrick Pantel, Eric Crestan, Arkady Borkovsky, Ana-Maria Popescu, and Vishnu Vyas. 2009.  Web-scale distributional similarity and entity set expansion.  In _Proceedings of the 2009 Conference on Empirical Methods in Natural Language Processing_ , pages 938–947.
  * Pennington et al. (2014) Jeffrey Pennington, Richard Socher, and Christopher D. Manning. 2014.  GloVe: Global vectors for word representation.  In _EMNLP 2014 - 2014 Conference on Empirical Methods in Natural Language Processing, Proceedings of the Conference_.
  * Rong et al. (2016) Xin Rong, Zhe Chen, Qiaozhu Mei, and Eytan Adar. 2016.  Egoset: Exploiting word ego-networks and user-generated ontology for multifaceted set expansion.  In _Proceedings of the Ninth ACM international conference on Web search and data mining_ , pages 645–654.
  * Russakovsky et al. (2015) Olga Russakovsky, Jia Deng, Hao Su, Jonathan Krause, Sanjeev Satheesh, Sean Ma, Zhiheng Huang, Andrej Karpathy, Aditya Khosla, Michael Bernstein, et al. 2015\.  Imagenet large scale visual recognition challenge.  _Int J Comput Vis_ , 115:211–252.
  * Shen et al. (2017) Jiaming Shen, Zeqiu Wu, Dongming Lei, Jingbo Shang, Xiang Ren, and Jiawei Han. 2017\.  Setexpan: Corpus-based set expansion via context feature selection and rank ensemble.  In _Joint European Conference on Machine Learning and Knowledge Discovery in Databases_ , pages 288–304. Springer.
  * Shen et al. (2018) Jiaming Shen, Zeqiu Wu, Dongming Lei, Chao Zhang, Xiang Ren, Michelle T Vanni, Brian M Sadler, and Jiawei Han. 2018.  Hiexpan: Task-guided taxonomy construction by hierarchical tree expansion.  In _Proceedings of the 24th ACM SIGKDD International Conference on Knowledge Discovery & Data Mining_, pages 2180–2189.
  * Tong and Dean (2008) Simon Tong and Jeff Dean. 2008.  System and methods for automatically creating lists.  US Patent 7,350,187.
  * Vilnis and McCallum (2015) L. Vilnis and A. McCallum. 2015.  Word representations via Gaussian embedding.  In _Proceedings of the 3rd International Conference on Learning Representations (ICLR)_.
  * Wang et al. (2008) Richard C Wang, Nico Schlaefer, William Cohen, and Eric Nyberg. 2008.  Automatic set expansion for list question answering.  In _Proceedings of the 2008 Conference on Empirical Methods in Natural Language Processing_ , pages 947–954.
  * Zhang et al. (2019a) Yan Zhang, Jonathon Hare, and Adam Prügel-Bennett. 2019a.  Deep Set Prediction Networks.  In _Advances in Neural Information Processing Systems 32_.
  * Zhang et al. (2019b) Yan Zhang, Jonathon Hare, and Adam Prügel-Bennett. 2019b.  Learning representations of sets through optimized permutations.  In _Proceedings of the International Conference on Learning Representations (ICLR)_.
  * Zhang et al. (2020) Yan Zhang, Jonathon Hare, and Adam Prügel-Bennett. 2020.  Fspool: Learning set representations with featurewise sort pooling.  In _Proceedings of the International Conference on Learning Representations (ICLR)_.