# Scaling Up Multiagent Reinforcement Learning for Robotic Systems:
Learn an Adaptive Sparse Communication Graph

Chuangchuang Sun, Macheng Shen, and Jonathan P. How ∗Laboratory for
Information and Decision Systems, Massachusetts Institute of Technology, 77
Massachusetts Ave, Cambridge, MA 02139.
Emails: {ccsun1, macshen<EMAIL_ADDRESS>
###### Abstract

The complexity of multiagent reinforcement learning (MARL) in multiagent
systems increases exponentially with respect to the agent number. This
scalability issue prevents MARL from being applied in large-scale multiagent
systems. However, one critical feature in MARL that is often neglected is that
the interactions between agents are quite sparse. Without exploiting this
sparsity structure, existing works aggregate information from all of the
agents and thus have a high sample complexity. To address this issue, we
propose an adaptive sparse attention mechanism by generalizing a sparsity-
inducing activation function. Then a sparse communication graph in MARL is
learned by graph neural networks based on this new attention mechanism.
Through this sparsity structure, the agents can communicate in an effective as
well as efficient way via only selectively attending to agents that matter the
most and thus the scale of the MARL problem is reduced with little optimality
compromised. Comparative results show that our algorithm can learn an
interpretable sparse structure and outperforms previous works by a significant
margin on applications involving a large-scale multiagent system.

##  I INTRODUCTION

Reinforcement Learning (RL) has achieved enormous successes in robotics [1]
and gaming [2] in both single and multiagent settings. For example, deep
reinforcement learning (DRL) achieved super-human performance in the two-
player game Go, which has a very high-dimensional state-action space [3, 4].
However, in multiagent scenarios, the sizes of the state space, joint action
space, and joint observation space grow exponentially with the number of
agents. As a result of this high dimensionality, existing multiagent
reinforcement learning (MARL) algorithms require significant computational
resources to learn an optimal policy, which impedes the application of MARL to
systems such as swarm robotics [5]. Thus, improving the scalability of MARL is
a necessary step towards building large-scale multiagent learning systems for
real-world applications.

In MARL, the increase of complexity of finding an optimal joint policy, with
respect to the number of agents, is a result of coupled interactions between
agents [6]. However, in many multiagent scenarios, the interactions between
agents are quite sparse. For example, in a soccer game, an agent typically
only needs to pay attention to other nearby agents when dribbling because
agents far away are not able to intercept. The existence of such sparsity
structures of the state transition dynamics (or the state-action-reward
relationships) suggests that an agent may only need to attend to information
from a small subset of the agents for near-optimal decision-making. Note that
the other players that require attention might not be nearby, such as the
receiver of a long pass in soccer. In such cases, the agent only needs to
selectively attend to agents that “matter the most”. As a result, the agent
can spatially and temporally reduce the scale of the planning problem.

In large-scale MARL, sample complexity is a bottleneck of scalability [7]. To
reduce the sample complexity, another feature we can exploit is the
interchangeability of homogeneous agents: switching two agents’ state/action
will not make any difference to the environment. This interchangeability
implies permutation-invariance of the multiagent state-action value function
(a.k.a. the centralized $Q$-function) as well as interchangeability of agent
policies. However, many MARL algorithms such as MADDPG [8], VDN [9], QMIX [10]
do not exploit this symmetry and thus have to learn this interchangeability
from experience, which increases the sample complexity unnecessarily.

Graph neural network (GNN) is a specific neural network architecture in which
permutation-invariance features can be embedded via graph pooling operations,
so this approach has been applied in MARL [11, 12, 13] to exploit the
interchangeability. As MARL is a non-structural scenario where the
links/connections between the nodes/agents are ambiguous to decide, a graph
has to be created in advance to apply GNN for MARL. Refs. [11, 12, 13], apply
ad-hoc methods, such as $k$-nearest neighbors, hard threshold, and random
dropout to obtain a graph structure. However, these methods require
handcrafted metrics to measure the closeness between agents, which are
scenario-specific and thus not general/principled. Inappropriately selecting
neighbors based on a poorly designed closeness metric could lead to the
failure of learning a useful policy.

While attention mechanisms [14] could be applied to learn the strength of the
connections between a pair of agents (i.e., closeness metric) in a general and
principled way, such strengths are often dense, leading to a nearly-complete
computation graph that does not benefit scalability. The dense attention
mechanism results from that the softmax activation function operated on the
raw attention logits generates a probability distribution with full support.
One solution to enforce a sparse graph is top $k$ thresholding [15], which
keeps the $k$-largest attention scores and truncates the rest to zero.
However, this truncation is a non-differentiable operation that may cause
problems for gradient-based optimization algorithms, such as those used in
end-to-end training. Therefore, a sparse attention mechanism that preserves
the gradient flow necessary for gradient-based training is required.

To address the non-differentiability issue in sparse attention mechanisms, we
generalize sparsemax [16] and obtain a sparsity mechanism whose pattern is
adaptive to the environment states. This sparsity mechanism can reduce the
complexity of both the forward pass and the back-propagation of the policy and
value networks, as well as preserving the end-to-end trainability in contrast
to hard thresholding. With the introduction of GNN and generalized sparsemax,
which can preserve permutation invariance and promote sparsity respectively,
the scalability of MARL is improved.

The discussion so far was restricted to homogeneous agents and thus
permutation-invariance is desirable. However, in heterogeneous multiagent
systems or competitive environments, permutation invariance and
interchangeability are no longer valid. For example, in soccer, switching
positions of two players from different sides can make a difference to the
game. To address this heterogeneity, GNN-based MARL must distinguish the
different semantic meanings of the connections between different agent pairs
(e.g. friend/friend relationship versus friend/foe relationship). We address
this requirement by multi-relational graph convolution network [17] to pass
messages using different graph convolution layers on graph edge connections
with different semantic meanings.

To summarize, we propose to learn an adaptive sparse communication graph
within the GNN-based framework to improve the scalability of MARL, which
applies to both homogeneous and heterogeneous multiagent systems in mixed
cooperative-competitive scenarios.

###  I-A Related Work

One of the existing works exploiting the structure in MARL is the mean-field
reinforcement learning (MFRL) [18] algorithm, which takes as input the
observation and the mean action of neighboring agents to make the decision,
and neglects the actions of all the other agents. This simplification leads to
good scalability. However, the mean action cannot distinguish the difference
among neighboring agents and the locality approximations fail to capture
information from a far but important agent for optimal decision-making, which
leads to sub-optimal policies. Multi-Actor-Attention-Critic (MAAC) is proposed
in [19] to aggregate information using attention mechanism from all the other
agents. Similarly, [11, 13, 20] also employ the attention mechanism to learn a
representation for the action-value function. However, the communication
graphs used there are either dense or ad-hoc ($k$ nearest neighbors), which
makes the learning difficult.

Sparse attention mechanisms were first studied by the natural language
processing community in [16], where sparsemax was proposed as a sparse
alternative to the activation function softmax. The basic idea is to project
the attention logits onto the probability simplex, which can generate zero
entries once the projection hits the boundary of the simplex. While
generalized sparse attention mechanisms were further studied in [21, 22, 23],
they are not adaptive to the state in the context of MARL, in terms of the
sparsity pattern.

Given this state of the art, the contributions of this paper are twofold.
First, we propose a new adaptive sparse attention mechanism in MARL to learn a
sparse communication graph, which improves the scalability of MARL by lowering
the sample complexity. Second, we extend our GNN-based MARL to heterogeneous
systems in mixed cooperative-competitive settings using multi-relational GNN.
The evaluations show that our algorithm significantly outperforms previous
approaches on applications involving a large number of agents. This technique
can be applied to empower large-scale autonomous systems such as swarm
robotics.

##  II PRELIMINARIES

###  II-A Multiagent Reinforcement Learning

As a multiagent extension of Markov decision processes (MDPs), a Markov game
is defined as a tuple $\langle N,S,\\{O_{i}\\}_{i\in N},\\{A_{i}\\}_{i\in
N},\\{r_{i}\\}_{i\in N},\gamma\rangle$, where $N=[1,\ldots,n]$ is a set of
agent indices, $S$ is the set of state, $\\{O_{i}\\}_{i\in N}$ and
$\\{A_{i}\\}_{i\in N}$ are the joint observation and joint action sets,
respectively. The $i$th agent chooses actions via a stochastic policy
$\pi_{\theta_{i}}:O_{i}\times A_{i}\to[0,1]$, which leads to the next state
according to the state transition function $\mathcal{T}:{S}\texttimes
A_{1}\texttimes\ldots\texttimes A_{n}\to S$. The $i$th agent also obtains a
reward as a function of the state and agent’s action
$r_{i}:S\texttimes\\{A_{i}\\}_{i\in N}\to\mbox{$\mathbb{R}$}$, and receives a
private observation correlated with the state $o_{i}:S\times\\{A_{i}\\}_{i\in
N}\to O_{i}$. The initial states are determined by a distribution
$\rho:S\to[0,1]$. The $i$th agent aims to maximize its own total expected
return $R_{i}=\sum_{t=1}^{T}\gamma^{t}r_{i}^{t}$, with discount factor
$\gamma$ and time horizon $T$.

###  II-B Multi-head attention

The scaled dot-product attention mechanism was first proposed in [14] for
natural language processing. An attention function maps the query and a set of
key-value pairs to the output, which is the weighted sum of the values. The
weight assigned to the each value calculated via a compatibility function of
the query and the corresponding key. In the context of MARL, let $h_{i},i\in
N$ be the representation of the agents. Key, query and value of agent $i$ is
defined as $K_{i}^{l}=W_{K}h_{i}^{l}\in\mathbb{R}^{d_{K}}$,
$Q_{i}^{l}=W_{Q}h_{i}^{l}$ and $V_{i}^{l}=W_{V}h_{i}^{l}$, respectively with
$W_{K},W_{Q}$ and $W_{V}$ are parameter matrices. The output for agent $i$ is
then

$\text{Att}_{i}(h)=\sum_{j}w_{ij}V_{j},$ (1)

where $w_{i\bullet}\in\mathbb{R}^{n}$, the $i$-th row of the weight matrix
$w$, is defined as

$w_{i\bullet}=\sigma_{a}\Big{(}\frac{(K_{i})^{T}Q}{\sqrt{d_{K}}}\Big{)}$ (2)

with $\sigma_{a}$ being the softmax function in previous works of GNN-based
MARL. The weight $w_{i\bullet}$ is dense as
$\operatorname*{softmax}_{i}(z)\neq 0$ for any vector $z$ and $i$.

To increase the expressiveness, multi-head attention is applied here via
simply concatenating the outputs from a single attention function [14].

###  II-C Relational GNN

In heterogeneous multiagent systems, different agent pair can have different
relations, such as friend or foe in a two-party zero-sum game. As a result,
information aggregation from agents with different relations should have
different parameters. Work in [17] proposed relational graph convolutional
network to model multi-relational data. The forward-pass update of agent $i$
in a multi-relational graph is as follows

$h_{i}^{(l+1)}=\sigma\Big{(}\sum_{r\in\mathcal{R}}\sum_{j\in\mathcal{N}_{i}^{r}}\frac{1}{c_{i,r}}W_{r}^{(l)}h_{j}^{(l)}+W_{0}^{(l)}h_{i}^{(l)}\Big{)},$
(3)

where $\mathcal{N}_{i}^{r}$ denotes the set of neighbor indices of agent $i$
under relation $r\in\mathcal{R}$ and $c_{i,r}$ is a normalization constant. To
distinguish the heterogeneity in MARL, similar to this convolution-based
multi-relational GNN, we apply different attention heads on agent pairs with
different relations.

##  III APPROACH

In this section, we present our approach to exploit the sparsity in MARL by
generalizing the dense soft-max attention to adaptive sparse attention.
Moreover, our approach to apply multi-relational attention mechanism for
heterogeneous games involving competitive agents is also introduced.

###  III-A Learning a communication graph via adaptive sparse attention

The scaled dot-product attention is applied to learn the communication graph
in MARL. If an attention weight between a pair of agents is zero, then there
is no communication/message passing between them. Thus, the normalization
function $\sigma_{a}(\bullet)$ in (2) is critical to learn a communication
graph. As usually used in the attention mechanism [14] or classifications,
$\sigma_{a}(\bullet)$ is usually set to be softmax, which cannot induce
sparsity. We propose an adaptive sparse activation function as an alternative
to softmax.

Let $x\in\mathbb{R}^{d}$ be the raw attention logits and $y$ be normalized
attention strength in the ($d-1$)-dimensional probability simplex defined as
$\Delta^{d}:=\\{y\in\mathbb{R}^{d}|y\geq 0,\textbf{1}^{T}y=1\\}$. We are
interested in the mapping from $x\in\mathbb{R}^{d}$ to $y\in\Delta^{d}$. In
other words, such a mapping can transform real weights to a probability
distribution, i.e., the normalized attention strength between a pair of
agents. The classical softmax, used in most attention mechanisms, is defined
component-wisely as

$y_{i}=\operatorname*{softmax}_{i}(x)=\frac{e^{x_{i}}}{\sum_{i=1}^{d}e^{x_{i}}}.$
(4)

A limitation of the softmax transformation is that the resulting probability
distribution always has full support, which makes the communication graph
dense, resulting in high complexity. In order to reduce the complexity, our
idea is to replace the softmax activation function with a generalized
activation function, which could adaptively be dense or sparse based on the
state. To investigate alternative activation functions to softmax, consider
the max operator defined as

$\max(x):=\max_{i\in[d]}(x_{i})=\sup_{y\in\Delta^{d}}y^{T}x,$ (5)

where $[d]=\\{1,\ldots,d\\}$. The second equality comes from that the supremum
of the linear form over a simplex is always achieved at a vertex, i.e., one of
the standard basis vector $\\{e_{i}\\}_{i\in[d]}$. As a result, the max
operator puts all the probability mass onto a single element, or in other
words, only one entry of $y$ is nonzero corresponding to the largest entry of
$x$. For example, with $x=[0,t]\in\mbox{$\mathbb{R}$}^{2}$, the probability
distribution w.r.t. the logit $t$, i.e.,
$(\operatorname*{arg\,sup}_{y\in\Delta^{d}}y^{T}x)_{2}$, is a step function,
as $(\operatorname*{arg\,sup}_{y\in\Delta^{d}}y^{T}x)_{2}$ equals 1 if $t>0$
and $0$ otherwise. This discontinuity at $t=0$ of the step function is not
amenable to gradient-based optimization algorithms for training deep neural
networks. One solution to the discontinuity issue encountered in (6) is to add
a regularized $\Omega(y)$ in the max operator as

$\Pi_{\Omega}(x)=\operatorname*{arg\,max}_{y\in\Delta^{d}}y^{T}x+\gamma\Omega(y)$
(6)

Different regularizers $\Omega(y)$ produce different mappings with distinct
properties (see summary in Table I). Note that with $\Omega(y)$ as the Shannon
entropy, $\Pi_{\Omega}(x)$ recovers softmax. With the states/observations
evolving, the ideal profile of $\Pi_{\Omega}(x)$ should be able to adapt the
sparsity extent (controlled via $\gamma$) and the pattern (controlled via the
selection of $\Omega(y)$) accordingly.

TABLE I: List of different regularizers and their corresponding mappings $y=\Pi_{\Omega}(x)$, where $x$ is the raw attention logits and $y$ is the probability distribution in $\Delta^{d}$.  Entropy | $\Omega(y)$ | $\Pi_{\Omega}(x)$ | Ref.
---|---|---|---
Shannon | $\sum_{i}y_{i}\log(y_{i})$ | $\operatorname*{softmax}_{i}(x)=\frac{e^{x_{i}}}{\sum_{i=1}^{d}e^{x_{i}}}$ | [22]
$l_{2}$ norm | $-\frac{1}{2}\sum_{i}y_{i}^{2}$ | $\arg\min_{y\in\Delta^{d}}\|y-x\|^{2}$ | [16]
Tsallis | $\left\\{\begin{array}[]{ll}\frac{\sum_{i}(y_{i}-y_{i}^{\alpha})}{\alpha(\alpha-1)},&\alpha\neq 1\\\ \sum_{i}y_{i}\log(y_{i}),&\alpha=1\end{array}\right.$ | No closed-form | [24]
Generalized | $\displaystyle\frac{1}{q}\sum_{i}(y_{i}-\frac{\displaystyle e^{qy_{i}}-1}{\displaystyle e^{q}-1})$ | No closed-form | [25]
TABLE II: List of different $G(x)$ and their resulting mappings $\Pi_{\Omega}(x)$ $\gamma G_{i}(x)$ | $\frac{e^{x_{i}}}{\sum_{i}e^{x_{i}}}$ | $\frac{{x_{i}^{2}}}{\sum_{i}{x_{i}^{2}}}$ | $x_{i}$
---|---|---|---
$\Pi_{\Omega}(x)$ | softmax | softmax | sparsemax
Property |  Translation invariance $\Pi_{\Omega}(x)=\Pi_{\Omega}(x+c\textbf{1})$ |  Scaling invariance $\Pi_{\Omega}(x)=\Pi_{\Omega}(cx)$ |  Translation invariance $\Pi_{\Omega}(x)=\Pi_{\Omega}(x+c\textbf{1})$
Example | $\Pi_{\Omega}([100,101])=\Pi_{\Omega}([0,1])$ | $\Pi_{\Omega}([1,2])=\Pi_{\Omega}([1,2]\times 10^{-3})$ | $\Pi_{\Omega}([100,101])=\Pi_{\Omega}([0,1])$

Note that the Tsallis entropy and the generalized entropy in Table I do not
have closed-form solutions [22], which will increase the computational burden
since iterative numerical algorithms will have to be employed. Sparsemax has a
closed-form solution and can induce sparsity, but sparsemax is not adaptive
and lacks flexibility as it is unable to switch from one sparsity pattern to
another when necessary. We aim to combine the advantages and avoid the
disadvantages using this new formulation

$\Pi_{\Omega}(x)=\operatorname*{arg\,min}_{y\in\Delta^{d}}||y-\gamma
G(x)||^{2},$ (7)

with $G(x):\mbox{$\mathbb{R}$}^{d}\to\mbox{$\mathbb{R}$}^{d}$ and $\gamma$
being a learnable neural network and a scalar, respectively. By choosing
different $G(x)$, $\Pi_{\Omega}(x)$ can exhibit different sparsity patterns
including softmax and sparsemax. With $G(x)$ fixed, the parameter $\gamma$ can
control how sparse the output could be, similar to the temperature parameter
in softmax. The summary in Table II shows that (7) will lead to a general
mapping and can combine properties such as translation and scaling invariance
adaptively. Work in [23] proposed sparse-hourglass that can adjust the trade-
off between translation and scaling invariance via tunable parameters.
However, it is unclear under which circumstances one property is more
desirable than the other, so there is little to no prior knowledge on how to
tune such parameters. In contrast, our formulation in (7) can balance such
trade-off via learning $G(x)$ and $\gamma$ while work in [23] is based on a
fixed form of $G(x)$ with tunable parameters.

While we can let the neural network learn
$G(x):\mbox{$\mathbb{R}$}^{d}\to\mbox{$\mathbb{R}$}^{d}$ without any
restrictions, there is indeed prior knowledge that we can apply, e.g.,
monotonicity. It is desired to keep the monotonicity of $\Pi_{\Omega}(x)$,
i.e., $\forall x_{i}>x_{j},(\Pi_{\Omega}(x))_{i}>(\Pi_{\Omega}(x)_{j}$, as
larger attention logit should be mapped into larger attention strength. As
sparsemax is monotonic, this requires that $\forall
x_{i}>x_{j},G_{i}(x)>G_{j}(x)$, or in other words, the order of the input of
$G(x)$ coincides with that of the output. To keep this property, $G(x)$ is
designed component-wisely as
$G_{i}(x)=\psi(\phi_{1}(x_{i}),\sum_{i}\phi_{2}(x_{i}))$, with
$\psi:\mbox{$\mathbb{R}$}^{2}\to\mbox{$\mathbb{R}$}^{1},\phi_{1},\phi_{2}:\mbox{$\mathbb{R}$}^{1}\to\mbox{$\mathbb{R}$}^{1}$
are neural networks with hidden layers. Note that $G_{i}(x)$ should be coupled
with all of the entries of $x$ instead of be a univariate function only
depending on $x_{i}$, as demonstrated in Table II. As the second argument of
$\psi$ (i.e., $\sum_{i}\phi_{2}(x_{i})$) is invariant to $G_{i}(x),\forall
i\in[d]$, the order preserving of
$G(x):\mbox{$\mathbb{R}$}^{d}\to\mbox{$\mathbb{R}$}^{d}$ is equivalent to the
monotonicity of $\psi(\bullet)$ and $\phi_{1}(\bullet)$. In order to keep this
monotonicity, we enforce all the weights of the networks $\psi$ and $\phi_{1}$
to be positive [26], by applying an absolute value function on the weights.
This architecture can accelerate the learning process with extra prior
knowledge, as it is monotonic by design.

###  III-B Message passing in MARL via GNN

We will present how the information is aggregated to learn a representation
for per-agent value/policy network using a graph neural network. The scaled
dot-product attention mechanism (Section II-B) with our generalized sparsemax
as the activation function, denoted as sparse-Att, is applied to learn a
communication graph and pass messages through the connections in the graph.

We start with homogeneous multiagent system, where the relation between any
agent pair is identical. A graph is defined as
$\mathcal{G}:=(\mathcal{V},\mathcal{E})$, where $v_{i}\in\mathcal{V}$
represent an agent and the cardinality of $\mathcal{V}$ is $|\mathcal{V}|$.
Moreover, $e_{ij}\in\mathcal{E}$ is $1$ if agent $i$ and $j$ can communicate
directly (or agent $j$ is observable to agent $i$), and $0$ otherwise. This is
a restriction on the communication graph and $\mathcal{E}$ is the set of all
possible edges. Then sparse-Att aims to learn a subset of $\mathcal{E}$ via
induced sparsity without compromising much optimality. For agent $i$, let
$U_{i}=f_{a}(X_{i})$ and $E_{i}$ be its observation and entity encoding
respectively, where $X_{i},i\in\mathcal{V}$ is the local state and $f_{a}$ is
a learnable agent encoder network. Then the initial observation embedding of
agent $i$, denoted as $h_{i}^{(1)}$, is

$h_{i}^{(1)}=f_{mp}(U_{i}\|E_{i}),$ (8)

where $f_{mp}$ is another learnable network and the operator $\|$ denotes
concatenation. Then at hop $l$ ($l$-th round of message passing), agent $i$
aggregates information from its possible neighbors belonging to the set
$\mathcal{N}=\\{j\in\mathcal{V}|e_{ij}=1\\}$ as follows

$h_{i}^{(l+1)}=f_{mp}\Big{(}h_{i}^{(l)}\|\text{sparse-
Att}_{i}^{\mathcal{N}}(h^{(l)})\Big{)}.$ (9)

With $l\geq 2$, the multi-hop message passing can enable the agent to obtain
information from beyond its immediate neighbors. In the message aggregation
from all of the agents $\mathcal{N}$, identical parameters are used in
$\text{sparse-Att}_{i}^{\mathcal{N}}$, which enforces the permutation-
invariance. This property is desirable because homogeneous agents are
interchangeable.

However, interchangeability is no longer applicable to heterogeneous systems
or mixed cooperative-competitive environment. For example, with
$\mathcal{V}_{1},\mathcal{V}_{2}\subseteq\mathcal{V}$ being a two-team
partition of $\mathcal{V}$, agents cooperate with other agents from the same
team but compete against agents from the other team. For agent
$i\in\mathcal{V}_{1}$, its teammate neighborhood and enemy neighborhood are
$\mathcal{N_{+}}=\\{j\in\mathcal{V}_{1}|e_{ij}=1\\}$ and
$\mathcal{N_{-}}=\\{j\in\mathcal{V}_{2}|e_{ij}=1\\}$, respectively. The edges
connecting teammates and enemies are called positive and negative edges. Then
based on multi-relational GNN, agent $i$ aggregates information at hop $l$ in
the following way

$h_{i}^{(l+1)}=f_{mp}\Big{(}h_{i}^{(l)}\|\text{sparse-
Att}_{i}^{\mathcal{N}_{+}}(h^{(l)})\|\text{sparse-
Att}_{i}^{\mathcal{N}_{-}}(h^{(l)})\Big{)},$

where $\text{sparse-Att}_{i}^{\mathcal{N}_{+}}$ and $\text{sparse-
Att}_{i}^{\mathcal{N}_{-}}$ are different attention heads. Additionally,
balance theory [27] suggests that “the teammate of my teammate is my teammate”
and “the enemy of my enemy is my teammate.” In a two-team competitive game,
any walk (a sequence of nodes and edges of a graph) between an agent pair in
the communication graph, comprising of both positive and negative edges, will
lead to the same relation between the agent pair [28]. This property
eliminates the ambiguity that the information aggregated from the same agent
(but different walk) might have a different teammate/enemy property.

Figure 1: Our sparse-Att framework consists of three modules: encoder, multi-
relational sparse attention mechanism, and value/policy network, with
homogeneous agents sharing all parameters. Agents employ different attention
heads to aggregate information alongside connections with different semantic
meanings, followed by a concatenation. $L$ is the number of the message-
passing rounds; see (9). “concat” denotes the concatenation operation. Here
only two classes (shown in red and blue) of heterogeneous agents are shown for
simplicity.

The proposed algorithmic framework is illustrated in Fig. 1. After $L$ rounds
of message passing, each agent has an updated encoding $h_{i}^{(L+1)}$. This
encoding is then fed into the value network and the policy network, which
estimate the state value and a probability distribution over all possible
actions, respectively. As homogeneous agents are interchangeable, they share
all of the parameters, including entity encoding, policy, value and message
passing. Proximal policy gradient (PPO, [29]) is employed to train the model
in an end-to-end manner. As only local information is required, the proposed
approach is decentralized. Moreover, our approach maintains the
transferability of GNN-based approaches as all the network dimensions are
invariant to agent/entity number in the system.

##  IV EXPERIMENTS

###  IV-A Task description

The proposed algorithm is evaluated in three swarm robotics tasks: Coverage,
Formation, and ParticleSoccer [30], first two of which are cooperative and the
third is competitive. The tasks are simulated in the Multiagent Particle
Environment111https://github.com/openai/multiagent-particle-envs(MAPE [8]).
The agents in MAPE can move in a 2-dimensional space following a double
integrator dynamic model. The action space of the agents is discretized, with
each agent can accelerate/decelerate in both $X$ and $Y$ direction. The three
tasks are briefly introduced as follows.

Coverage: There are $n_{A}$ agents (light purple) and $n_{L}$ landmarks
(black) in the environment (see illustration in Fig. 2(a)). The objective for
the agents is to cover the landmarks with the smallest possible number of
timesteps. Agents are not assigned to reach a certain landmark, but instead,
have to figure out the assignment via communication such that the task can be
finished optimally.

Formation: There are $n_{A}$ agents (blue) and $1$ landmarks (black) in the
environment (see illustration in Fig. 2(b)), with $n_{A}$ being an even
natural number. The agents need to split into two sub-teams of equal size,
with each of them building a formation of a regular pentagon. The two regular
pentagons with different sizes are both centered at the landmark.

ParticleSoccer: There are $n_{A}$ agents and 3 landmarks in the environment
(see illustration in Fig. 2(c)), with the bigger landmark as a movable ball
and the two smaller ones as a fixed landmark. A team wins the game via pushing
the black ball to the opponent team’s goal. The goal color of the light blue
(red, resp.) team is blue (red, resp.).

(a) Coverage

(b) Formation

(c) ParticleSoccer

Figure 2: Three different simulation tasks used in this work.

###  IV-B Implementation specifications

The agent encoder $f_{a}(\bullet)$ and the entity encoder take input the
$4$-dimensional agent states and $2$-dimensional entity states, respectively.
The queries, keys, and values in all of the sparse attention mechanism are
$128$-dimensional. The communication hop is $L=2$. All neural networks are
fully connected with the ReLU activation function. In the sparsity-promoting
function (7), $\phi_{1},\phi_{2}$ and $\psi$ all have one hidden layer with
dimensions being $16$, $16$ and $64$, respectively. The absolute value
function is used to keep the weights of the monotonicity-preserving neural
network positive.

Evaluation is performed every $320$ episodes and PPO update is executed for
$4$ epochs after collecting experience of $4096$ timesteps.

###  IV-C Results

In the cooperative scenarios i.e., Coverage and Formation, two metrics are
used to evaluate the algorithms. The first is the average reward per step and
the second is the task success rate. Higher means better performance for both
metrics.

We compare our algorithms with two baselines: GNN-based MARL with dense
attention mechanism [11] and MAAC [19]. These two algorithms are considered to
be strong baselines as they reported advantageous results against algorithms
including MADDPG [8], COMA [31], VDN [32] and QMIX [10]. Public
repositories222https://github.com/sumitsk/matrl.git333
https://github.com/shariqiqbal2810/MAAC are used for comparison. As both
repositories also apply their algorithms on MAPE, the default hyperparameters
are used for comparison.

In simulation, we set $n_{A}=30$ and $n_{A}=20$ for Coverage and Formation,
respectively. Fig. 4 and Fig. 4 demonstrated that our algorithm can achieve
higher rewards than the two baselines with fewer episodes. This validates that
sparse-Att can accelerate the learning process via aggregating information
from agents that matter the most. Moreover, in terms of the second metric,
i.e., success rate, our algorithm consistently outperforms the two baselines
by a significant margin (with a much smaller variance), as shown in Fig. 5.
The evaluations of both metrics for two scenarios provide strong support for
the advantages of our algorithm.

Figure 3: Reward comparison of our algorithm against two baselines for the
Coverage task.

Figure 4: Reward comparison of our algorithm against two baselines for the
Formation task.

(a) Coverage

(b) Formation

Figure 5: Performance comparison of three algorithm on two scenarios. Multiple
policies learned from each algorithm are evaluated and the mean/standard
deviation are plotted.

For the competitive ParticleSoccer task, we set $n_{A}=20$ with both red team
and blue team of size $\frac{n_{A}}{2}=10$. As this task is competitive, the
above two metrics are no longer applicable. Instead, we let the red (blue,
resp.) play against a blue (red, resp.) team from another algorithm. Table III
presents the results of the inter-algorithm competition. The overall score of
each algorithm equals the sum of the winning evaluation episodes of its red
team and blue team playing against blue and red team respectively from other
algorithms. The overall scores in Table III show that our algorithm can learn
strong policies.

TABLE III: Evaluation of three algorithms in the competitive ParticleSoccer task. Each pair is evaluated for $50$ episodes and the $(\bullet,\bullet,\bullet)$ in each cell denotes the number of red team winning episodes, blue team wining episodes and the draw episodes. A draw means that neither team scores within a given episode length. $\text{win}_{\text{red}}$ and $\text{win}_{\text{blue}}$ are the winning episodes of the red and blue team, respectively when competing against blue and red team from other algorithms. Red Blue |  sparse-Att (ours) | dense-Att | MAAC | $\text{win}_{\text{red}}$
---|---|---|---|---
sparse-Att (ours) |  blue!25$(48,0,2)$ | $(15,0,35)$ | $(26,0,24)$ | $41$
dense-Att | $(9,1,40)$ |  blue!25$(5,0,45)$ | $(3,0,47)$ | $11$
MAAC | (7,0,43) | (2,0,48) |  blue!25$(3,0,47)$ | $9$
$\text{win}_{\text{blue}}$ | $-15$ | $-17$ | $-29$ | N/A
|  sparse-Att (ours) | dense-Att | MAAC |
overall scores: $\text{win}_{\text{red}}+\text{win}_{\text{blue}}$ | $\mathbf{26}$ | $-6$ | $-20$ |

###  IV-D Interpretability of the sparse communication graph

Let us proceed by considering the inherent sparity in Formation and
ParticleSoccer. As mentioned in the description of the Formation scenario, the
formation of each pentagon is related to half of the agents, while the sub-
team assignments need to be learned. In the implementation, the reward is set
to require that the first $\frac{n_{A}}{2}$ agents closest to the landmark
build the formations of the inner pentagon and the remaining $\frac{n_{A}}{2}$
agents to build the formations of the outer pentagon. With the convergence of
the learning algorithm, once a sub-team partition is learned to complete the
two sub-tasks, the learned agent indexing of each team should not vary due to
the distance sorting and the two pentagons are relatively far away. As a
result, the reward to complete each sub-task is only related to the
corresponding sub-team and hence the two sub-teams are decoupled from each
other. The adjacency matrix of the learned communication graph shown in Fig.
6(a) validates that the inter-team communication is very sparse. This
adjacency matrix is up to row/column permutation as indexing of each sub-team
is learned without being known as a prior. Moreover, in a sub-team, the
algorithm learns a communication graph similar to a star-graph. It can be
understood that each sub-team selects a leader. As a star-graph is a connected
graph with possibly minimum edges, this communication protocol is both
effective and efficient. Also, the length of the path between any agent pair
in a star graph is no greater than $2$, which echos the two-hop communication
($L=2$) we used in the simulation. That is because due to the two-hop message-
passing, the agents can eventually communicate with agents as far as two edges
away, which includes all of the agents in a star graph. Note that the sparsity
on the diagonal entries of the communication graph does not mean that the
agent’s own information is neglected, as it is separately concatenated; see
(9).

Also, in the ParticleSoccer scenario, from each team’s perspective, agents
need to coordinate tightly within the team to greedily push the ball to the
other team’s goal while only attending to a small number of agents from the
other team. This leads to dense intra-team communication but relatively sparse
inter-team communication. This is validated by the approximately block-
diagonal adjacency matrix of the learned communication graph in Fig. 6(b).

(a) Coverage

(b) Formation

Figure 6: Sparse communication graph for two scenarios. For the Coverage, our
sparse-Att learns to split into two sub-team as desired and the learned sparse
star-like communication graph makes communication both effective and
efficient. In the ParticleSoccer, sparse-Att learn to pay more attention to
teammates and a necessary subset of enemies.

##  V CONCLUSIONS and FUTURE WORK

This paper exploits sparsity to scale up Multi-Agent Reinforcement Learning
(MARL), which is motivated by the fact that interactions are often sparse in
multiagent systems. We propose a new general and adaptive sparsity-inducing
activation function to empower an attention mechanism, which can learn a
sparse communication graph among agents. The sparse communication graph can
make the message-passing both effective and efficient such that the
scalability of MARL is improved without compromising optimality. Our algorithm
outperforms two baselines by a significant margin on three tasks. Moreover,
for scenarios with inherent sparsity, it is shown that the sparsity of the
learned communication graph is interpretable.

Future work will focus on combining evolutionary population curriculum
learning and graph neural network to further improve the scalability. In
addition, robust learning against evolving/learned adversarial attacks is also
of great interest.

## ACKNOWLEDGMENTS

Research is supported by Scientific Systems Company, Inc. under research
agreement $\\#$ SC-1661-04. Authors would like to thank Dong-Ki Kim, Samir
Wadhwania and Michael Everett for their many useful discussions and Amazon Web
Services for computation support.

## References

  * [1] J. Kober, J. A. Bagnell, and J. Peters, “Reinforcement learning in robotics: A survey,” _The International Journal of Robotics Research_ , vol. 32, no. 11, pp. 1238–1274, 2013.
  * [2] V. Mnih, K. Kavukcuoglu, D. Silver, A. A. Rusu, J. Veness, M. G. Bellemare, A. Graves, M. Riedmiller, A. K. Fidjeland, G. Ostrovski, _et al._ , “Human-level control through deep reinforcement learning,” _Nature_ , vol. 518, no. 7540, pp. 529–533, 2015.
  * [3] D. Silver, A. Huang, C. J. Maddison, A. Guez, L. Sifre, G. Van Den Driessche, J. Schrittwieser, I. Antonoglou, V. Panneershelvam, M. Lanctot, _et al._ , “Mastering the game of go with deep neural networks and tree search,” _nature_ , vol. 529, no. 7587, p. 484, 2016.
  * [4] D. Silver, J. Schrittwieser, K. Simonyan, I. Antonoglou, A. Huang, A. Guez, T. Hubert, L. Baker, M. Lai, A. Bolton, _et al._ , “Mastering the game of go without human knowledge,” _Nature_ , vol. 550, no. 7676, pp. 354–359, 2017.
  * [5] M. Hüttenrauch, A. Šošić, and G. Neumann, “Guided deep reinforcement learning for swarm systems,” _arXiv preprint arXiv:1709.06011_ , 2017.
  * [6] D. S. Bernstein, R. Givan, N. Immerman, and S. Zilberstein, “The complexity of decentralized control of markov decision processes,” _Mathematics of operations research_ , vol. 27, no. 4, pp. 819–840, 2002.
  * [7] L. Bu, R. Babu, B. De Schutter, _et al._ , “A comprehensive survey of multiagent reinforcement learning,” _IEEE Transactions on Systems, Man, and Cybernetics, Part C (Applications and Reviews)_ , vol. 38, no. 2, pp. 156–172, 2008.
  * [8] R. Lowe, Y. Wu, A. Tamar, J. Harb, O. P. Abbeel, and I. Mordatch, “Multi-agent actor-critic for mixed cooperative-competitive environments,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 6379–6390.
  * [9] P. Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, J. Z. Leibo, K. Tuyls, _et al._ , “Value-decomposition networks for cooperative multi-agent learning based on team reward,” in _Proceedings of the 17th International Conference on Autonomous Agents and MultiAgent Systems_. International Foundation for Autonomous Agents and Multiagent Systems, 2018, pp. 2085–2087.
  * [10] T. Rashid, M. Samvelyan, C. S. De Witt, G. Farquhar, J. Foerster, and S. Whiteson, “QMIX: monotonic value function factorisation for deep multi-agent reinforcement learning,” _arXiv preprint arXiv:1803.11485_ , 2018\.
  * [11] A. Agarwal, S. Kumar, and K. Sycara, “Learning transferable cooperative behavior in multi-agent teams,” _arXiv preprint arXiv:1906.01202_ , 2019\.
  * [12] A. Khan, E. Tolstaya, A. Ribeiro, and V. Kumar, “Graph policy gradients for large scale robot control,” _arXiv preprint arXiv:1907.03822_ , 2019.
  * [13] J. Jiang, C. Dun, and Z. Lu, “Graph convolutional reinforcement learning for multi-agent cooperation,” _arXiv preprint arXiv:1810.09202_ , vol. 2, no. 3, 2018.
  * [14] A. Vaswani, N. Shazeer, N. Parmar, J. Uszkoreit, L. Jones, A. N. Gomez, Ł. Kaiser, and I. Polosukhin, “Attention is all you need,” in _Advances in neural information processing systems_ , 2017, pp. 5998–6008.
  * [15] J. K. Chorowski, D. Bahdanau, D. Serdyuk, K. Cho, and Y. Bengio, “Attention-based models for speech recognition,” in _Advances in neural information processing systems_ , 2015, pp. 577–585.
  * [16] A. Martins and R. Astudillo, “From softmax to sparsemax: A sparse model of attention and multi-label classification,” in _International Conference on Machine Learning_ , 2016, pp. 1614–1623.
  * [17] M. Schlichtkrull, T. N. Kipf, P. Bloem, R. Van Den Berg, I. Titov, and M. Welling, “Modeling relational data with graph convolutional networks,” in _European Semantic Web Conference_. Springer, 2018, pp. 593–607.
  * [18] Y. Yang, R. Luo, M. Li, M. Zhou, W. Zhang, and J. Wang, “Mean field multi-agent reinforcement learning,” _arXiv preprint arXiv:1802.05438_ , 2018\.
  * [19] S. Iqbal and F. Sha, “Actor-attention-critic for multi-agent reinforcement learning,” _arXiv preprint arXiv:1810.02912_ , 2018.
  * [20] A. Das, T. Gervet, J. Romoff, D. Batra, D. Parikh, M. Rabbat, and J. Pineau, “Tarmac: Targeted multi-agent communication,” _arXiv preprint arXiv:1810.11187_ , 2018.
  * [21] V. Niculae and M. Blondel, “A regularized framework for sparse and structured neural attention,” in _Advances in Neural Information Processing Systems_ , 2017, pp. 3338–3348.
  * [22] M. Blondel, A. F. Martins, and V. Niculae, “Learning classifiers with fenchel-young losses: Generalized entropies, margins, and algorithms,” _arXiv preprint arXiv:1805.09717_ , 2018.
  * [23] A. Laha, S. A. Chemmengath, P. Agrawal, M. Khapra, K. Sankaranarayanan, and H. G. Ramaswamy, “On controllable sparse alternatives to softmax,” in _Advances in Neural Information Processing Systems_ , 2018, pp. 6422–6432.
  * [24] G. M. Correia, V. Niculae, and A. F. Martins, “Adaptively sparse transformers,” _arXiv preprint arXiv:1909.00015_ , 2019.
  * [25] A. M. Kowalski, R. D. Rossignoli, and E. M. Curado, _Concepts and recent advances in Generalized Information Measures and Statistics_. Bentham Science Publishers, 2013.
  * [26] C. Dugas, Y. Bengio, F. Bélisle, C. Nadeau, and R. Garcia, “Incorporating functional knowledge in neural networks,” _Journal of Machine Learning Research_ , vol. 10, no. Jun, pp. 1239–1262, 2009.
  * [27] F. Heider, “Attitudes and cognitive organization,” _The Journal of psychology_ , vol. 21, no. 1, pp. 107–112, 1946.
  * [28] D. Easley, J. Kleinberg, _et al._ , “Networks, crowds, and markets: Reasoning about a highly connected world,” _Significance_ , vol. 9, pp. 43–44, 2012.
  * [29] J. Schulman, F. Wolski, P. Dhariwal, A. Radford, and O. Klimov, “Proximal policy optimization algorithms,” _arXiv preprint arXiv:1707.06347_ , 2017\.
  * [30] E. Şahin, “Swarm robotics: From sources of inspiration to domains of application,” in _International workshop on swarm robotics_. Springer, 2004, pp. 10–20.
  * [31] J. N. Foerster, G. Farquhar, T. Afouras, N. Nardelli, and S. Whiteson, “Counterfactual multi-agent policy gradients,” in _Thirty-second AAAI conference on artificial intelligence_ , 2018.
  * [32] P. Sunehag, G. Lever, A. Gruslys, W. M. Czarnecki, V. Zambaldi, M. Jaderberg, M. Lanctot, N. Sonnerat, J. Z. Leibo, K. Tuyls, _et al._ , “Value-decomposition networks for cooperative multi-agent learning,” _arXiv preprint arXiv:1706.05296_ , 2017.


# A Twitter-Driven Deep Learning Mechanism for the Determination of Vehicle
Hijacking Spots in Cities

Taahir Aiyoob Patel, Clement N. Nyirenda  _Department of Computer Science,_
_Faculty of Natural Sciences,_
_The University of the Western Cape_
_Bellville, Cape Town 7535_
_South Africa_
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Vehicle hijacking is one of the leading crimes in many cities. For instance,
in South Africa, drivers must constantly remain vigilant on the road in order
to ensure that they do not become hijacking victims. This work is aimed at
developing a map depicting hijacking spots in a city by using Twitter data.
Tweets, which include the keyword “hijacking”, are obtained in a designated
city of Cape Town, in this work. In order to extract relevant tweets, these
tweets are analyzed by using the following machine learning techniques: 1) a
Multi-layer Feed-forward Neural Network (MLFNN); 2) Convolutional Neural
Network; and Bidirectional Encoder Representations from Transformers (BERT).
Through training and testing, CNN achieved an accuracy of 99.66%, while MLFNN
and BERT achieve accuracies of 98.99% and 73.99% respectively. In terms of
Recall, Precision and F1-score, CNN also achieved the best results. Therefore,
CNN was used for the identification of relevant tweets. The relevant reports
that it generates are visually presented on a points map of the City of Cape
Town. This work used a small dataset of 426 tweets. In future, the use of
evolutionary computation will be explored for purposes of optimizing the deep
learning models. A mobile application is under development to make this
information usable by the general public.

###### Index Terms:

Twitter, Deep Learning, Vehicle Hijacking, Artificial Neural Networks

##  I Introduction

Drivers are constantly at risk of being hijacked. Locals may be able to avoid
certain areas due to personal knowledge; it is, however, not uncommon to fall
victim nonetheless. As the number of drivers increases, the risk becomes
greater. Between July and September 2021, in South Africa there was a total of
4973 hijackings [1]. This shows the magnitude of the issue.

Social media platforms such as twitter provide a constant flow of information.
Twitter, itself, is commonly known for allowing users to discuss their daily
thoughts and events. It is also used by news outlets to inform users of
current real-time events. This inspires the research of using Twitter as a
real-time data source for car hijacking incident reports. Obtaining hijacking
crime data from Law enforcement agencies can be a difficult task, for reasons
such as there not being updated collections of data, or perhaps difficulty in
obtaining administrative approval. Generally, the supplied reports and
analytical data are usually presented in large time increments, such as
monthly, annually, etc. Therefore, with the use of Twitter as the main source
of data obtainment, the data can be used and updated in real-time. However, an
issue arises from using social media as the data source, and that is the issue
of relevancy. Due to the lack of restrictions on tweets, a large amount of the
obtained tweets could be irrelevant to the topic. For example, searching for
tweets containing the keyword of hijacking, would return incident report
tweets, as well as tweets discussing a different topic, however containing the
keyword. Therefore, there is a need for machine learning to separate the off-
topic irrelevant tweets, from the relevant incident reports.

Piña‐García and Ramírez‐Ramírez [2] proposed using a linear predictive model
to evaluate the performance of google trends in predicting crime rates based
on a weekly analysis. This was done by presenting multiple sections in the
report which addressed different factors influencing the proposal such as a
section presenting heatmaps of the number of crimes in Mexico City by per
borough, then by neighborhoods [2]. They were able to prove that Google trends
and Twitter can be used to generate estimates of crime occurrences. They
presented this by using a linear predictive model. This proposal introduced
the possibility of using Google trends and Twitter to track crime trends and
analysing it further to gain relevant information.

Mata et al [3] developed an application to help locate safe routes of travel
using estimations defined from crime rates. They demonstrated their proposal
by providing the algorithms and pseudo code they used, as well as examples of
their proposed application user interface performing the proposed
functionalities. Through their research, they were able to obtain the safest
traveling route by using the Bayes algorithm with a certainty degree of around
75% effectiveness [3]. Their research provides further insight for the
research done in this paper by using Twitter to gain the reports.

Lal et al [4] obtained and analysed a total of 369 tweets into classes of
Crime and Not-Crime respectively. To conduct their study they used a text
minding approach whereby they employed 4 main classifiers for testing, namely
Naive Bayesian (NB), Random Forest (RF), J48 and ZeroR. The RF classifier
performed the best with an accuracy value of 98.1%, but it had the longest
model building time of 7.24s. On the other hand, the ZeroR classifier was the
worst performing classifier. In terms receiver operating characteristic (ROC)
analysis, NB, J48, and RF gave gave the best performance [4].

The work in [4] inspired the work proposed in this paper. While Twitter has
been used for generic crime prediction, so far no work has been reported on
Twitter-based determination of vehicle hijacking spots. Since Twitter contains
both relevant and irrelevant or fake tweets, the need for the determination of
relevant tweets by performing classification of “hijacking” and “non-
hijacking” arises naturally. Therefore, this paper addresses this issue by
using a similarly small datasets to the one that was used in [4]. While the
work in [4] used shallow learning techniques, this work uses three deep
learning techniques, namely: a Convolutional Neural Network (CNN), an Multi-
layer Feed Forward Neural Network (MLFNN), and a Bidirectional Encoder
Representations from Transformers (BERT) model. These models are trained by
using 296 tweets and tested by using 130 tweets. The best performing model is
adopted and used to identify relevant hijacking reports from the tweets
database, and the vehicle hijacking locations are extracted from the tweets to
indicate them on the visual maps of hijacking spots. In this study, the City
of Cape Town is used. But the approach can be used in any city as long as the
tweets are in English.

This paper is organised as follows. A brief overview into the Machine Learning
mechanisms used in this work is presented in Section II. Section III presents
the materials and methods we employed in this work. The results are presented
in Section IV. Lastly, the paper is concluded in Section V.

##  II A Brief Overview on Deep Learning Mechanisms Employed in This Work

This section presents a brief overview on the three machine learning
algorithms used in this work.

###  II-A Multi-Layer Feed-Forward Neural Network

A Multi-Layer Feed-Forward Neural Network [5] is a neural network whereby each
layer is fully connected to each other to the subsequent layer. It consists of
an input layer, output layer, as well as a number of hidden layers. A MLFNN is
generally used for supervised learning, which implies that the model is
trained using a dataset of inputs and their correct outputs. When training a
MLFNN, the model is given a set of $N$ input-output($x$,$y$) pairs $X$. The
training process involves the constant iterations of updating values of the
weights of the perceptrons $j$ in layers $l_{k}$ for the incoming node $i$, as
well as the bias $b^{k}_{i}$ for the output $o_{i}$ on the input $x_{i}$, with
the aim of minimizing the mean squared error [6], which is given by

$E(X)=\frac{1}{2N}\sum_{i=1}^{N}(o_{i}-y_{i})^{2}\,$ (1)

###  II-B Convolutional Neural Network

Convolutional Neural Network(CNN) [7] is generally comprised of 3 types of
layers, namely Convolutional layers, Max Pooling layers, and lastly the fully-
connected layers. The Convolutional layer is aimed at outputting a high value
for a given position if there is a convolutional feature in the given
position, otherwise, a low value is outputted [8]. This value is obtained by
using

$h_{i,j}=\sum_{k=1}^{m}\sum_{l=1}^{m}w_{k,l}{x_{i+k-1,j+l-1}}\,$ (2)

where $m$ is the kernel width and height, $h$ is the convolution output, $X$
is the input, and $W$ is the convolution kernel. The max pooling layer is
aimed at outputting the maximum value of the input which falls on the kernel
[8], which is defined by

$p_{i,j}=max\\{w_{i+k-1,j+l-1}\forall{1\leq k\leq m\>and\>1\leq l\leq m}\\}\,$
(3)

A CNN is generally aimed at image recognition. Due to the nature of CNN for
image data, the standard format is Conv2D. However, in this work, a one
dimensional CNN, Conv1D is employed because of the textual data that is being
used.

###  II-C Bidirectional Encoder Representations from Transformers

The bidirectional Encoder Representations from Transformers(BERT) model [9]
employs Transformers, which allow it to learn the contextual relationship
between words of a sentence. The BERT model was adopted with the aim of
implementing Transfer learning. Text classification is a common area of
interest for transfer learning, due the advancement of Natural Language
Processing (NLP). The BERT model incorporates a multi-layer bidirectional
Transformer encoder which comprises of a stack of 6 identical layers, with
each having a set of two sub-layers [10]. The first sub layer is a multi-head
self-attention mechanism, whereas the second is a position-wise fully
connected feed-forward network. For the multi-head self-attention, the scaled
dot-product attention is required, which is defined by

$Attention(Q,K,V)=softmax(\frac{QK^{T}}{\sqrt{d_{k}}})V,$ (4)

where $Q$, $K$, $V$, are the matrices of the queries, keys, values
respectively, and $d_{k}$ is the dimension of the matrices, $Q$ and $K$. The
multi-heads $head_{i}$ are computed by using

$head_{i}=Attention(QW^{Q}_{i},KW^{K}_{i},VW^{V}_{i})$ (5)

where $QW$,$KW$, and $VW$, are the query, key, and value matrices
respectively. From this, the multi-head self-attention is performed by using

$MultiHead(Q,K,V)=Concat(head_{1},....,head_{h})W^{O}$ (6)

where $W$ is a weight matrix.

##  III Materials and Methods

This section presents the materials and methods that were used in order to
realize the goals of this study. First of all, two sets of datasets had to be
generated for training and for testing processes. After that, data was
processed in order to align with the deep learning models used in this study.
Finally the models were trained and testing was conducted. These approaches
are explained in detail in the next subsections. The system flow diagram can
be seen in Fig. 1.

Figure 1: System flow diagram

###  III-A Data Generation and Pre-processing

This work is concerned with obtaining raw, unedited tweets, and understanding
whether they denote genuine hijacking reports, or they are just irrelevant
tweets. For purposes of this study, the City of Cape was chosen as the target
area. Tweets containing the words ”hijacking” and ”Cape Town” were collected
by using a small python program focusing on tweets in a 50km radius from the
center of Cape Town. This was done with the Tweepy [11] python library. This
data was then pushed into a MySQL data for storage. The total number of tweets
collected was 426. These tweets were extracted into a into an Excel
spreadsheet, where each tweet was then manually indicated as relevant or
irrelevant by applying a code of 1 and 0 respectively. There were eventually
divided into two sets as follows: 1) 296 tweets constituted the training
set(76 relevant, 220 irrelevant); 2) 130 constituted the testing set (29
relevant, 101 irrelevant).

To prepare the data for training, standard pre-processing was conducted
whereby leading or trailing spaces were removed followed by converting the
text to lower case, and lastly, removing stop words. Inspired by the work of
Wang et al [12], the TfidfVectorizer was also incorporated in the MLFNN and
CNN mechanisms. For text classification with Natural Language Processing
(NLP), there are multiple different strategies to do this, such as the Bag-of-
Words methods like the Term Frequency - Inverse Document Frequency (TF-IDF)
method, or through language models such as BERT, or perhaps through Word2Vec,
such as the approach of Jang et al [13]. The TF-IDF identifies the number of
occurrences of a word in a document, as well as the measure of the rarity of
the word in the document. The BERT method incorporates the ELMo context
embedding [14], as well as multiple Transformers. For BERT, each vector which
is assigned to a word, is a function of the sentence as a whole, therefore,
based on the context each word has the possibility of having more than one
vector [15]. As a result, the TfidfVectorizer was not required for the BERT
implementation.

###  III-B Training and Testing

TensorFlow [16] and Python 3.8 were used to train the model. The Adam
optimizer was used for optimization, along with the binary cross-entropy loss.
A batch size of 32 was used over 20 epochs. A validation split of 0.2 was also
incorporated. The training was done on a home desktop with a single AMD RX570
GPU running a Windows 10 Operating System.

The following performance metrics were used:

  * •

Accuracy: This is a percentage measurement of how well the model predicted a
true value. This is done during the training and validation phase.

  * •

Loss: This is the summation of the number of errors the model makes. The loss
function, binary cross-entropy performs a calculation of the difference
between the actual value, and predicted values. It then provides a penalty
score based on how far the predicted value is from the actual. This was
calculated during the training and validation phase.

  * •

Precision: This is the measurement of how much the model correctly predicted a
positive, over the number of positive predictions as a whole.

  * •

Recall: This is the measurement of how much the model correctly predicted a
positive, over all the actual positives.

  * •

F1-score: This is the weighted averages of the Precision and Recall.

Precision, recall, and F1-score are used during testing. This approach was
adopted from the work in [4, 17]. The Accuracy and F1-Score were also used in
the CNN implementation in [13].

Model specific measures for the training process were implemented as follows:

  1. 1.

Convolutional Neural Network: For the development of the CNN, the base model
consisted of a single Convolutional and Max Pooling Layer. The performance of
this model was used as a base, then the number of layers was increased by
adding Convolutional and Max Pooling layers. This was done twice, increasing
the number of Convolution and MaxPooling layers by 1 each time. Three models
were therefore obtained: Single Conv1D/MaxPooling; Double Conv1D/MaxPooling;
and Triple Conv1D/MaxPooling. Fig. 2 illustrates the Double Conv1D/Maxpooling
architecture.

Figure 2: The Double Conv1D/Maxpooling architecture.

  2. 2.

Multi-Layer Feed-Forward Neural Network: Similar to the CNN, a base model was
selected and the layout was adjusted to compare performance. The base model
was influenced by the work in [12]. The initial model that was selected
comprised of 2 Dense Layers. The number of layers was then increased by 1 each
time and the performance was observed before selecting the preferred model.
Fig. 3 illustrates the MLFNN architecture with four dense layers.

Figure 3: The MLFNN architecture with four dense layers.

  3. 3.

Bidirectional Encoder Representations from Transformers: When working with
Transfer learning and BERT, the focus is more on the fine-tuning aspect of
BERT. A common way of doing this, is by adjusting the learning rate. The
learning rates employed, were according to [18] and their research on BERT,
whereby they employed learning rates: 5e-5; 4e-5; 3e-5; and 2e-5. The accuracy
measurements, as well as the other previously mentioned performance metrics
were then observed, before selecting the preferred model. Fig. 4 illustrates
the BERT architecture with four dense layers.

Figure 4: BERT Model Architecture.

##  IV Results and Discussion

This section presents the results obtained from the three models after varying
model specific parameters in order to obtain the highest performance for a
model on the aforementioned metrics during training, validation and testing.
Discussions on how the best parameter settings were determined are also
conducted.

###  IV-A Convolutinal Neural Network

As previously mentioned, 3 CNN architectures were created, a single
Conv1D/MaxPooling, a double Conv1D/MaxPooling, and a triple Conv1D/MaxPooling.
These models were then trained and tested, and the performance was captured.
Table I shows training accuracy and loss along with validation accuracy and
loss for three CNN architectures during training. Whereas, Table II shows
precision, recall and F1-score for the three architectures during testing.
From these results, there was not much difference amongst the CNN models.
However, it was observed that the 2 Conv1D/MaxPooling layer architecture,
performed slightly better in the accuracy and loss measurements, as well as in
the precision score. Therefore, it was selected as the preferred model.

TABLE I: CNN Model Comparison during Training CNN Model Accuracy and Loss
---
Architecture |  TrainAcc |  TrainLoss |  ValAcc |  ValLoss
1 Conv1D |  0.9899 |  0.0507 |  0.9500 |  0.2140
2 Conv1D |  0.9966 |  0.0370 |  0.9833 |  0.1800
3 Conv1D |  0.9831 |  0.0690 |  0.9167 |  0.3404
TABLE II: CNN Model Comparison during Testing CNN Model Precision, Recall and
F1-Score
---
Architecture |  Precision |  Recall |  F1-Score
1 Conv1D |  0.9545 |  0.7241 |  0.8235
2 Conv1D |  0.9565 |  0.7586 |  0.8462
3 Conv1D |  0.9231 |  0.8276 |  0.8727

###  IV-B Multi-Layer Feed-Forward Neural Network

As mentioned, when creating the model architecture, 3 models of varying number
of dense layers(2 layer model, 3 layer model, 4 layer model) were created.
Table III displays the accuracy and loss measurements of the MLFNN models
during training, whereas Table IV displays the performance metrics of the
three MLFNN architectures during testing. It is shown that the 2 Dense layer
architecture, achieved the best scores in the precision, recall, and F1-score,
but only by a slight difference, as well has having the same recall value as
the 4 Dense layer architecture. However, the 4 Dense layer architecture, had
the lowest loss values amongst the 3, as well as sharing the highest accuracy
measurements with the 3 Dense layer architecture. Therefore, the 4 Dense layer
architecture was selected as the preferred MLFNN model. The model layout is
shown in Fig. 3.

TABLE III: MLFNN Model Comparison during Training CNN Model Accuracy and Loss
---
Architecture |  TrainAcc |  TrainLoss |  ValAcc |  ValLoss
2 Dense |  0.9865 |  0.3207 |  0.9333 |  0.4598
3 Dense |  0.9899 |  0.0692 |  0.9500 |  0.2303
4 Dense |  0.9899 |  0.0397 |  0.9500 |  0.1858
TABLE IV: MLFNN Model Comparison during Testing CNN Model Precision, Recall
and F1-Score
---
Architecture |  Precision |  Recall |  F1-Score
2 Dense |  1.0 |  0.7241 |  0.8400
3 Dense |  0.9524 |  0.6897 |  0.8000
4 Dense |  0.9546 |  0.7241 |  0.8235

###  IV-C Bidirectional Encoder Representations from Transformers

Lastly, for the development of the BERT model, as mentioned the actual layout
of the BERT model was not altered. However the fine-tuning method of adjusting
the learning rates was employed. The employed learning rates of 2e-5, 3e-5,
4e-5, and 5e-5, in accordance with [18]. From this, the best performing model
was selected as the preferred model. Table V presents the accuracy and loss
measurements of the four BERT architectures during training. On the other
hand, Table VI presents the performance metrics of the four architectures
during testing. As shown in these results, two of the learning rates, namely
3e-5, and 5e-5, returned 0.0 for Precision, Recall, and F1-score, and are
therefore not able to be the preferred model. Amongst 2e-5 and 4e-5, 2e-5
obtained higher Precision, Recall, and F1-score, however achieved lower
accuracy and loss values. Therefore, the model with the learning rate 2e-5 was
selected as the preferred BERT model.

TABLE V: BERT Model Comparison during Training BERT Model Accuracy and Loss
---
Learning Rate |  TrainAcc |  TrainLoss |  ValAcc |  ValLoss
2e-5 |  0.7399 |  0.6168 |  0.8500 |  0.5771
3e-5 |  0.7432 |  0.5515 |  0.9000 |  0.4742
4e-5 |  0.7466 |  0.5498 |  0.9000 |  0.4659
5e-5 |  0.7432 |  0.5544 |  0.9000 |  0.4517
TABLE VI: BERT Model Comparison during Testing BERT Model Precision, Recall
and F1-Score
---
Learning Rate |  Precision |  Recall |  F1-Score
2e-5 |  0.2857 |  0.0699 |  0.1111
3e-5 |  0.0 |  0.0 |  0.0
4e-5 |  0.1667 |  0.0345 |  0.0571
5e-5 |  0.0 |  0.0 |  0.0

###  IV-D Discussion

Now with the three preferred models from each type, the selection of the final
model is required. These performances are collated in Table VII and Table
VIII. From these results, the CNN model performed performs slightly better
than the MLFNN. The BERT model however, proved to not only be inefficient, as
the training time taken was much longer than the CNN and the MLFNN, it also
provided undesirable results, as shown by the performance metrics. This lines
up similarly with [19], whereby they compared BERT with Learning and Teaching
Support Material (LSTM) on a small dataset, and found the LTSM to perform
better than the BERT model. From everything discussed, it is concluded that
the CNN is the preferred model for the task in question and was therefore
employed as the text classification model, to assist in the obtainment of
hijacking incident reports from the tweets database.

TABLE VII: Model Comparison Model Accuracy and Loss
---
Architecture |  TrainAcc |  TrainLoss |  ValAcc |  ValLoss
CNN |  0.9966 |  0.0370 |  0.9833 |  0.1800
MLFNN |  0.9899 |  0.0397 |  0.9500 |  0.1858
BERT |  0.7399 |  0.6168 |  0.8500 |  0.5771
TABLE VIII: Model Comparison 2 Model Precision, Recall and F1-Score
---
Architecture |  Precision |  Recall |  F1-Score
CNN |  0.9565 |  0.7586 |  0.8462
MLFNN |  0.9546 |  0.7241 |  0.8235
BERT |  0.2857 |  0.0699 |  0.1111

###  IV-E Vehicle Hijacking Maps

As mentioned, the goal of devising and obtaining a machine learning model was
to determine relevant tweets relating to hijackings in the Cape Town area. The
tweets that were deemed relevant by the CNN model were processed further in
order to extract the locations mentioned in the text in order to plot them on
the maps. In order to obtain the locations, the Geopy [20] python library was
used. Next, Geograpy [21] was used to obtain the coordinates of these
locations. This information was used to create a heat-map, as well as a point-
map by employing the Gmaps [22] library. The point-map of hijacking spots, in
Fig. 5, displays the locations mentioned in the CNN identified relevant
tweets.

Figure 5: Cape Town Point-map for hijacking spots

##  V Conclusion

This work was aimed at devising a deep learning learning model for text
classification of relevant tweets containing the keyword ”hijacking”. The goal
was to use Twitter as a data source of hijacking reports to display the
incident locations on maps for visualisation. Three deep learning models, were
therefore trained on 296 tweets and tested on 130 tweets. These models are as
follows: a Convolutional Neural Network (CNN), a Multi-Layer Feed-Forward
Neural Network (MLFNN), and a Bidirectional Encoder Representations from
Transformers (BERT) model. The CNN and MLFNN were tested with varying
architectures, and the BERT model was tested with varying learning rates.
Through testing and observation, it was found that the CNN model was the
highest performing model. It was, therefore, employed to identify relevant
tweets from a database of tweets containing the keyword ”hijacking”. Through
this, the relevant hijacking tweets were identified, and the in-text mentioned
locations of the incidents were extracted. This allowed for the creation of
the point-map of hijacking spots in the Cape Town area.

In the future, the use of evolutionary computation will be explored with the
aim of optimizing the deep learning models. Furthermore, a mobile application
is under development to make this information usable by the general public.

## References

  * [1] BusinessTech, ”Hijackings on the rise in South Africa – here are the hotspot areas,” BusinessTech, Nov. 19, 2021. [Online]. Available: https://businesstech.co.za/news/lifestyle/539516/hijackings-on-the-rise-in-south-africa-here-are-the-hotspot-areas/
  * [2] C. A. Piña‐García and L. Ramírez‐Ramírez, “Exploring crime patterns in Mexico City,” Journal of Big Data, vol. 6, no. 65, p. 21, 2019.
  * [3] F. Mata, M. Torres-Ruiz, G. Guzmán, R. Quintero, R. Zagal-Flores, M. Moreno-Ibarra and E. Loza, “A Mobile Information System Based on Crowd-Sensed and Official Crime Data for Finding Safe Routes: A Case Study of Mexico City,” Mobile Information Systems, vol. 2016, p. 11, 2016.
  * [4] S. Lal, L. Tiwari, R. Ranjan, A. Verma, N. Sardana, R. Mourya, ”Analysis and Classification of Crime Tweets,” Procedia Computer Science, vol. 167, pp. 1911-1919, 2020.
  * [5] Tushar Gupta, ”Deep Learning: Feedforward Neural Network,” Towards Data Science, Jan. 5, 2017. Accessed on: Feb. 12, 2022. [Online]. Available: https://towardsdatascience.com/deep-learning-feedforward-neural-network-26a6705dbdc7
  * [6] Brilliant ”Feedforward Neural Networks,” Brilliant.org, [Online]. Available: https://brilliant.org/wiki/feedforward-neural-networks/
  * [7] IBM Cloud Education, ”Convolutional Neural Networks,” IBM Cloud Education, Oct. 20, 2020. Accessed on: Feb. 12, 2022. [Online]. Available: https://www.ibm.com/cloud/learn/convolutional-neural-networks
  * [8] T. Ganegedara, ”Intuitive Guide to Convolution Neural Networks,” Towards Data Science, May 31, 2018. [Online]. Available: https://towardsdatascience.com/light-on-math-machine-learning-intuitive-guide-to-convolution-neural-networks-e3f054dd5daa
  * [9] R. Horev, ”BERT Explained: State of the art language model for NLP,” Towards Data Science, Nov. 10, 2018. [Online]. Available: https://towardsdatascience.com/bert-explained-state-of-the-art-language-model-for-nlp-f8b21a9b6270
  * [10] S. González-Carvajal, E.C. Garrido-Merchán, ”Comparing BERT against traditional machine learning text classification,” ArXiv, 2020.
  * [11] J. Roesslein, “Tweepy Documentation,” [Online]. Available: https://docs.tweepy.org/en/stable/index.html
  * [12] K. Wang, R. Chen and E. Xin, “TwitterRelevanceClassification,” June 4, 2020. [Online]. Available: https://github.com/wang0324/TwitterRelevanceClassification.
  * [13] B. Jang, I. Kim, J.W. Kim, ”Word2vec convolutional neural networks for classification of news articles and tweets”,PLoS ONE, vol. 14,8, Aug 2019.
  * [14] J. Taylor, ”ELMo: Contextual language embedding,” Towards Data Science, Jan. 6, 2019. [Online]. Available: https://towardsdatascience.com/elmo-contextual-language-embedding-335de2268604
  * [15] M.D. Pietro, ”Text Classification with NLP: Tf-Idf vs Word2Vec vs BERT,” Towards Data Science, July 18, 2020. [Online]. Available: https://towardsdatascience.com/text-classification-with-nlp-tf-idf-vs-word2vec-vs-bert-41ff868d1794
  * [16] Google Brain Team, ”TensorFlow: Large-Scale Machine Learning on Heterogeneous Systems,” 2015. [Online]. Available: https://www.tensorflow.org/
  * [17] Y. Luan, S. Lin, ”Research on Text Classification Based on CNN and LSTM”,2019 IEEE International Conference on Artificial Intelligence and Computer Applications, pp. 352-355, March 2019.
  * [18] J. Delvin, M.-W. Chang, K. Lee, K. Toutanova, ”BERT: Pre-training of Deep Bidirectional Transformers for Language Understanding”, ArXiv,vol. abs/1810.04805, 2019.
  * [19] A. Ezen-Can, ”A Comparison of LSTM and BERT for Small Corpus”, ArXiv, vol. abs/2009.05451, 2020.
  * [20] GeoPy Contributors Revision, “Welcome to GeoPy’s documentation!,” [Online]. Available: https://geopy.readthedocs.io/en/stable/
  * [21] S. Rakshit, “geograpy3 0.1.28,” [Online]. Available: https://pypi.org/project/geograpy3/.
  * [22] Google, “Google Maps,” Google, [Online]. Available: https://www.google.com/maps.