# Reward Shaping Using Convolutional Neural Network

Hani Sami  Hadi Otrok  Jamal Bentahar  Azzam Mourad  Concordia Institute for
Information Systems Engineering, Concordia University, Montreal, Canada
Center of Cyber-Physical Systems (C2PS), Department of EECS, Khalifa
University, Abu Dhabi, UAE  Department of Computer Science and Mathematics,
Lebanese American University, Beirut, Lebanon  Division of Science, New York
University, Abu Dhabi, UAE  Ernesto Damiani

###### Abstract

In this paper, we propose Value Iteration Network for Reward Shaping (VIN-RS),
a potential-based reward shaping mechanism using Convolutional Neural Network
(CNN). The proposed VIN-RS embeds a CNN trained on computed labels using the
message passing mechanism of the Hidden Markov Model. The CNN processes images
or graphs of the environment to predict the shaping values. Recent work on
reward shaping still has limitations towards training on a representation of
the Markov Decision Process (MDP) and building an estimate of the transition
matrix. The advantage of VIN-RS is to construct an effective potential
function from an estimated MDP while automatically inferring the environment
transition matrix. The proposed VIN-RS estimates the transition matrix through
a self-learned convolution filter while extracting environment details from
the input frames or sampled graphs. Due to (1) the previous success of using
message passing for reward shaping; and (2) the CNN planning behavior, we use
these messages to train the CNN of VIN-RS. Experiments are performed on
tabular games, Atari 2600 and MuJoCo, for discrete and continuous action
space. Our results illustrate promising improvements in the learning speed and
maximum cumulative reward compared to the state-of-the-art.

###### keywords:

Reinforcement Learning, Reward Shaping, CNN, VIN, Message Passing, Atari,
MuJoCo

††journal: Information Sciences

##  1 Introduction

A Reinforcement learning (RL) algorithm is executed against a Markov Decision
Process (MDP) environment. The MDP environment is sketched by the solution
designer where the agent can perform actions decided by RL. The agent sends
feedback to the RL solution with a reward value to update the value function
based on the actions taken. Therefore, an accurate representation of the
reward function is vital for future action selection. Hence, dynamicity in the
structure of the reward function is required to adapt to environmental changes
and produce more effective rewards. Consequently, better rewards lead to
faster convergence to near optimality with regard to agent decisions. MDP
environments have different types with continuous or discrete, finite or
infinite states, and action spaces. Furthermore, a transition matrix deciding
the next state of the agent is most of the time unknown. These MDP properties
make it challenging to develop a scalable and dynamic reward function [15].

RL algorithms are slow to converge, where most of the time is spent on
exploration at the early stages of learning. There are multiple learning
speedup techniques for RL such as offline learning, dynamic exploration,
transfer learning, imitation learning, and reward shaping [23, 1]. Reward
shaping alters the original reward function with values generated from a
shaping function. The shaping values speed learning in RL by directing the
reward function to speed the policy convergence [13]. One of the reward
shaping mechanisms is potential-based, which ensures that updates to the
original reward function do not affect the ability of an agent to reach
optimal policy decisions. Due to the different types of MDP and dynamicity of
the environment, it is difficult to design a scalable and effective potential
function for reward shaping that is suitable for most environments [2]. The
existing reward shaping solutions suffer from one or more of the following
limitations: (1) they alter the optimal policy; (2) they are based on action
exploration only [5]; (3) they are not applicable in different environments;
(4) they rely on transition matrix approximation; (5) have limited
representation of sampled MDPs. The negative consequence of the first
limitation is that obtaining the optimal policy cannot be guaranteed. Because
of the second limitation, the reward function is never adapted to the
environment. Due to the other limitations, the agent performance based on the
potential function can be improved. The applicability of a reward shaping
solution is measured by the performance in various environments and the
dependability on external knowledge like expert feedback. Therefore, a
potential-based reward shaping solution is still an open problem. Hence, we
propose in this paper a novel potential-based reward shaping solution that is
scalable, learns on a representation of the MDP either through frames of
images or sampled MDP graphs, and estimates a transition matrix while
training.

The proposed potential function architecture follows the mechanism of the
Value Iteration Network (VIN) and uses convolution layers to perform planning
[24]. The original VIN module in [24] uses a Convolutional Neural Network
(CNN) architecture, which can be trained using RL or Imitation Learning (IL).
The CNN of the VIN can perform value iteration on an MDP for planning. The
output of the CNN is part of an attention mechanism that selects actions as
part of the optimal plan. In [24], learning is either done using IL, thus
requiring a large number of labels, or using RL whose performance is poor on
irregular graphs. Irregular graphs are problematic when training VIN with RL
because the number of actions for the neighbors varies.

The proposed VIN-RS trains a novel CNN based on the probabilistic view of RL
to serve as a potential function. Our new scheme, named Value Iteration
Network for Reward Shaping (VIN-RS), incorporates this novel training mode and
new architecture tailored for reward shaping. Computing message passing on
Hidden Markov Models (HMM) [26], composed of forward and backward messages,
derives the probability of trajectory optimality, thus can be used to redirect
the reward function and speed learning [26, 10]. Computing these messages in a
large environment requires high computation as discussed further in Section
3.4. On one hand, message passing helps the agent decide if the current state
belongs to an optimal trajectory. On the other hand, the CNN module of VIN
provides a goal-oriented plan for an optimal trajectory. In this paper, we
will argue that the message passing and VIN combined would help accelerate
learning by acting as the potential function. Therefore, we aim to train the
proposed CNN of VIN-RS based on the message passing loss computed from sampled
trajectories followed by the agent.

In[10], the authors propose a potential-based reward shaping solution using
Graph Convolution Network (GCN). GCN has the potential in propagating the
forward and backward messages of HMM using the graph operation for sharing
information between nodes. Despite significant improvement achieved over
existing reward shaping solutions, using GCN as the potential function still
has some limitations, and it cannot generalize to all environments. Even
though both CNN and GCN belong to the family of Graph Neural Networks (GNN),
GCN performs message passing on a sample of the states, while CNN uses full
images of the environment, which can reveal more states and speed planning. In
addition, to perform the GCN layer operation, the transition matrix of the MDP
should be estimated [10]. Assuming that the value function is smooth over the
MDP graph, the graph Laplacian is used as an approximation of the transition
matrix, resulting in a margin of error [17]. Furthermore, GCN has issues
related to MDP representation and information extraction, which is due to the
graph approximation technique used to represent the environment. Compared to
GCN, the proposed CNN learns a representation of this transition matrix while
training. More specifically, VIN-RS estimates a new MDP, not necessarily
related to the original one, which is learned using images of the environment
and trained following the message passing values. Even when the environment is
not captured as images, VIN-RS can train the CNN on a graph representation
from this environment, which leads to promising performance as illustrated
later in our experiments.

Training VIN-RS for reward shaping requires the true labels that are inferred
using message passing. Therefore, the loss function incorporates the message
passing mechanism. Due to (1) the computation complexity induced by
calculating the message passing; and (2) the difficulty of retrieving and
sometimes approximating the transition matrix of the environment, we train CNN
on image frames or samples of the environment graph capturing the current
state of the agent. CNN uses a transition matrix that is trained as part of
the network. The output of the proposed CNN is a regression value for each
possible action in the environment that estimates if the current state of the
agent belongs to an optimal trajectory. Furthermore, VIN-RS embeds the look-
ahead advice mechanism [28]. By evaluating the state and action, the look-
ahead advice improves the quality of the potential function and thus can
improve the learning speed using reward shaping. Thus, VIN-RS produces advice
at the state and action levels, which is at the core of the look-ahead advice
mechanism. In addition, it is possible to apply our solution in discrete and
continuous action spaces.

The contributions of this paper are summarized as follows:

  1. 1.

VIN-RS for potential-based reward shaping using a novel CNN architecture.

  2. 2.

CNN trained on images or graphs from the environment while using a message
passing mechanism in the loss function.

  3. 3.

Estimating the transition matrix through training the CNN.

  4. 4.

Overcoming the limitations of using GCN for reward shaping as the potential
function by training on an estimated MDP using CNN.

  5. 5.

State-of-the-art results in most of the games for discrete and continuous
action spaces.

The structure of the paper is divided as follows. In We describe the related
work in Section 2. In Section 3, we present the background required to cover
the core concepts of our approach. In Section 4, we present our proposed
reward shaping solution "VIN-RS". The evaluations conducted on tabular, Atari
and MuJoCo games are illustrated in Section 5. The results of our evaluation
shows that VIN-RS achieves on average the best results in the Atari and MuJoCo
games compared to all baselines. Finally, we summarize and conclude the paper
in Section 6 with future directions.

##  2 Related Work

Reward shaping has gained more attention in the past years due to the
importance of speeding the learning process in Deep RL [12], especially in
applications requiring real-time feedback. In this section, we first describe
VIN and its applications. Second, we discuss existing reward shaping solutions
and their limitations. Third, we discuss and present the limitations of recent
literature solutions that utilize deep learning to build the potential
function.

###  2.1 Value Iteration Networks and Applications

In [24], a VIN module is proposed to perform planning on a new MDP extracted
from images of the environment. The motivation behind VIN is to support
planning in NNs by integrating a new value iteration method inspired by the
policy updates in RL. The value of the work comes from using the convolution
operators to perform value iteration on an unknown MDP that outputs an optimal
trajectory. The states and actions of this MDP are the same as the original
MDP, while the reward and transition functions are any differentiable
functions that can be learned from the model while training. One of the main
limitations of VIN is that it can be applied using imitation learning which
requires a lot of ground truth labels or RL that provides poor performance.
Furthermore, VIN supports low-dimensional environments or MDPs only. Due to
the importance of the planning feature in NNs, various works extended form
[24] and proposed new differentiable reward and transition functions that can
stabilize learning in the network. For example, the authors in [14] proposes a
novel convolution operator to learn and plan on spatial and irregular graphs.

Various applications use VIN to combine planning with a supervised learning
task to improve the quality of the decisions. For instance, the work in [11]
utilizes VIN to perform UAV planning and adapt to novel physical locations.
Furthermore, the work in [29] uses VIN to learn urban navigation planning.

In this work, we propose a new variation of VIN, named VIN-RS, for the first
time in the context of potential-based reward shaping. VIN-RS encodes a new
training mode with message passing as part of the loss function. Our VIN-RS
can effectively plan trajectories to speed learning in the original policy.
VIN-RS takes images of the environment as input to output shaping values. The
shaping values are used in the form of potential-based reward shaping by
appending the original reward function.

###  2.2 Existing Reward Shaping Methods

There exist various reward shaping solutions that (1) alter the optimal
policy, (2) target action exploration instead of reward signal, or (3)
requires human intervention. For instance, Learning Intrinsic Rewards for
Policy Gradients (LIRPG) proposes an optimal reward framework and does not
guarantee invariance of the optimal policy [30]. The Random Network
Distillation (RND) approach provides an action exploration method to
accelerate learning [4]. RND uses an exploration bonus, which is calculated
using the error of a NN that predicts the observation features. The proposed
RND solution provides Superior performance in the challenging Montezuma
Revenge game. In [16], authors propose the intrinsic curiosity module (ICM) to
speed learning using action exploration. In ICM, the authors formulate
exploration by the error of the agent when trying to predict the consequences
of its actions [16]. In contrast to RND and ICM, our proposed VIN-RS offers
reward shaping based on the reward signal and not the exploration bonus. In
[10], the authors proposed a potential-based reward shaping solution that
performs message passing using GCN. More details about the GCN solution are
provided in the next subsection. In Section 5, we compare the performance of
VIN-RS to LIRPG [30], RND [4], ICM [16], and GCN [10].

###  2.3 Using GCN for Reward Shaping

Existing reward shaping solutions requires a neural network to become scalable
and accomodate for dynamicity in the environment with large state or action
spaces. For instance, the work in [6] suffers from scalability issues, while
[8] demands human intervention to update the reward function with feedbacks.
Therefore, we study the related work proposing to build the potential function
through deep learning to overcome the mentioned problems. In specific, the
most suitable deep learning models belong to the family of Graph Neural
Network (GNN), such as GCN. Hence, we discuss the two most related work that
uses GCN to build the value function [10, 19]. The GCN is capable of
recursively propagate messages among neighboring nodes in the graph,
determining its relation and importance. When using message passing of HMM,
those messages reveal more information about the state or trajectory of state
optimality, thus enlightening the original reward function about useful
information among the selected path. In [10], an improvement of learning speed
and reward achieved are presented for the first time when using GCN as a
reward shaping function. Despite its performance, the presented mechanism
suffers from various limitations including the representation of the sampled
MDP as a sub-graph of sampled transitions, and the approximation of the
transition matrix using graph Laplacian, which results in a margin of error
affecting its performance.

In this paper, we replace GCN with a VIN-RS that utilizes a CNN to perform
reward shaping as a potential function. In addition, GCN utilizes a subset of
the states and forms a graph that is passed to GCN for training. However,
using VIN-RS, we pass images of the environment as input to train the
potential function; therefore, more knowledge is provided with a larger set of
states. Furthermore, using GCN to compute the message passing requires an
approximation of the transition matrix. In this case, the graph Laplacian is
utilized [10]. Due to many drawbacks of using graph Laplacian as analyzed in
[17], reward shaping using GCN affects the performance. Several methods were
proposed to construct bases for Value Function Approximation (VFA), such as
using the graph Laplacian. It is proven that the graph Laplacian can only
produce effective VFA when assuming that the latter is smooth over the induced
MDP graph. Therefore, using the graph Laplacian to approximate the transition
matrix cannot generalize to all MDPs [17]. In our previous work [19], the
graph Laplacian is replaced by a Krylov subspace computed using the augmented
Krylov [17], as an attempt to overcome the graph Laplacian limitations.
However, this method still cannot guarantee an improvement over GCN in some
cases. Therefore, we replace in this work GCN by a CNN. In the proposed VIN-
RS, the probability transition matrix within the convolution layers is learned
when training the CNN network, thus avoiding the burden of approximating this
matrix.

##  3 Background

A modeled MDP environment $\mathcal{M}$ requires a clear definition of the
state space $\mathcal{S}$, action space $\mathcal{A}$, and reward function
$r$. As part of the MDP, $\gamma$ is also predefined to a value close to one
indicating the amount of information to propagate during the value function
updates in cumulative future steps. Furthermore, a transition matrix $P$ is
defined to foster the transitions from previous state to next state following
an action decided through exploration or exploitation. Thus, an MDP is
represented by the following tuple $(\mathcal{S},\mathcal{A},P,r,\gamma)$. The
policy $\pi$ is formed through deterministic or stochastic updates based on
the environment feedback from the environmnet to maximize the cumulative
future discounted rewards. In this work, we focus on value function updates
calculated as follows:
$\mathcal{V}_{n+1}(s)=\text{max}_{a}\mathcal{Q}_{n}(s,a)$, where
$\mathcal{Q}_{n}(s,a)=r(s,a)+\gamma\sum_{s^{\prime}}\mathcal{P}(s^{\prime}|s,a)\mathcal{V}_{n}(s^{\prime})$,
$s\in\mathcal{S}$ and $a\in\mathcal{A}$. An optimal value function
$\mathcal{V}^{*}(s)$ is the maximal return obtained over steps for all
trajectories. When $n\rightarrow\infty$, the value function $V_{n}$ converges.
Thus an optimal policy $\pi^{*}$ is obtained as follows:
$\pi^{*}(s)=\text{argmax}_{a}Q_{\infty}(s,a).$

###  3.1 Reward Shaping

A reward shaping is the process of updating the reward value by a shaping
value produced using a shaping function. This shaping value is computed by
passing the current and next states to the shaping function. We denote the
shaping function as $F$ and the updated reward function takes the following
form:

$R(s,a,s^{\prime})=r(s,a)+F(s,s^{\prime})$ (1)

where $F(s,s^{\prime})$ is the shaping function. In terms of potential-based
reward shaping, the shaping function is computed as follows [28]:

$F(s,s^{\prime})=\gamma\phi(s^{\prime})-\phi(s)$ (2)

where $\phi$ is a potential-shaping function. More explanation of previous
approaches proposing shaping functions is described in Section 2.

###  3.2 Convolutional Neural Network

The CNN network is proven to be successful in computer vision and natural
language processing applications. Furthermore, CNN layers extract features
from the images as it goes deeper into the network. The input layer in a CNN
takes as input raw image pixels which are three-dimensional. A CNN is composed
of convolutional layer, non-linearity layer, max pooling layer, and fully
connected layer. At each convolutional (conv) layer, there is a kernel matrix
or filter with a certain size. Setting the filter size is considered a
hyperparameter. A filter for the current layer is applied on the input matrix,
where matrix multiplication takes place. In addition, a sliding window or
stride on the input matrix can be applied so that more information about the
image can be concluded. Adding more layers with various filters results, in
most cases, in more feature extraction from the input matrix. Furthermore,
padding can be added to the images to not lose any information present at the
frame or edges of the matrix.

###  3.3 Value Iteration Network

A VIN incorporates planning inside a policy of the original MDP $\mathcal{M}$
by performing value iteration using a CNN [24]. It is assumed that VIN tries
to learn and solve another MDP $\bar{\mathcal{M}}$. Similar to any MDP,
$\bar{\mathcal{M}}$ has states, actions, reward and transition functions
denoted as
$\bar{{s}}\in\bar{\mathcal{S}},\bar{{a}}\in\bar{\mathcal{A}},\bar{\mathcal{R}}(\bar{{s}},\bar{{a}}),\text{and
}\bar{\mathcal{P}}(\bar{{s^{\prime}}}|\bar{{s}},\bar{{a}})$ respectively. The
state and action spaces in $\bar{\mathcal{M}}$ are similar to $\mathcal{M}$.
The reward and transition matrices of $\bar{\mathcal{M}}$ depend on the
observations of $\mathcal{M}$, i.e. $\bar{\mathcal{R}}=f_{r}(\phi(s))$ and
$\bar{\mathcal{P}}=f_{p}(\phi(s))$. The functions of the reward and transition
($f_{r}$ and $f_{p}$) are learned during the policy training of
$\bar{\mathcal{M}}$ using the CNN. The learned policy of $\bar{\mathcal{M}}$
is connected to obtaining the optimal policy of $\mathcal{M}$, even though the
reward and transition functions are not the same. The input to the VIN model
is a list of images extracted from the environment. The first layer in the CNN
of VIN is a convolution (Conv) layer that processes raw pixels and pass them
to the second layer. The first step in value iteration at the second conv
layer is to convert the input of the previous layer into a reward matrix using
the reward function $f_{r}$. The filter/kernel of this second conv layer is
considered as the probability transition matrix of $\bar{\mathcal{M}}$. In
addition, the third conv layer contains the $\mathcal{Q}$ value or state-
action value function over the channels of this layer for $\bar{\mathcal{M}}$.
Finally, this last layer is max-pooled to produce the next value iteration
$\bar{\mathcal{V}}$.

The output of VIN is only for a subset of states. Therefore, the output is
passed to an attention module that helps reduce the number of parameters to
train or the actions to focus on. Furthermore, the output of the attention
model is passed to the policy update of $\mathcal{M}$ to guide the model in
selecting better actions. The CNN is trained using the standard
backpropagation to support RL or IL decisions.

###  3.4 HMM and Message Passing

As part of the probability inference view in RL, the MDP is converted to an
HMM by adding the binary optimality variable $O$, where $1$ at $t$ means that
$S_{t}$ is optimal, and $0$ otherwise. The probability of $O=1$ given the
state and action taken at $t$ is inferred using a probability distribution
$p$, computed using function $f$ that maps rewards to probabilities:
$p(O_{t}=1|S_{t},A_{t})=f(r(S_{t},A_{t}))$.

This structure is presented in Figure 1, and is analogous to HMMs.

Figure 1: MDP structure as a graphical model treated as HMM

A backward message is computed as follows:
$\beta(S_{t},A_{t})=p(O_{t:T}|S_{t},A_{t})$. In this equation, $\beta$ refers
to an approximation of the cumulative reward over the trajectory from $t$ to
$T$ [26, 31]. Computing the backward message is a generalization of the
optimal control problem [18]. A forward message is computed as follows:
$\alpha(S_{t},A_{t})=p(O_{t_{0}:t-1})|S_{t},A_{t})p(S_{t},A_{t})$. This
message allows the agent to examine the trajectory optimality from $0$ to
$t-1$. Combining the forward and backward messages reveals information about
the full trajectory, which relevant and effective for building the potential
function in reward shaping.

##  4 Proposed Scheme: VIN-RS

Figure 2: An architecture incorporating the Value Iteration Network for Reward
Shaping with Reinforcement Learning

In this section, we start first by describing the overall proposed
architecture which consists of three main components: (1) VIN-RS, (2) message
passing, and (3) reinforcement learning algorithm. We describe each of the
components and list the steps for constructing the potential function of our
reward shaping solution using CNN and focus on the advantage of incorporating
the look-ahead advice mechanism. We also discuss the technique to obtain the
message passing values, which are used to compute the loss for the CNN. In
addition, we show an algorithm to train VIN-RS. Finally, the policy update
combining the output of CNN is presented in the main reinforcement learning
algorithm.

###  4.1 Overall Architecture

In Figure 2, we show the overall proposed architecture that combines VIN-RS
with RL. Our solution contains two main modules, the first is VIN-RS that uses
a CNN on $\bar{\mathcal{M}}$, while the second is the main RL solution for the
original MDP $\mathcal{M}$.

Starting with the main component which is the RL algorithm that computes the
policy $\pi$ to solve $\mathcal{M}$. The input to the RL module is the list of
states which can either be images or states representation from the
environment. These states are also called observations. Based on the
observations, the agent selects the best action according to the policy $\pi$,
then executes that action in the environment. The agent then receives the next
state as well as the reward of the action taken in the environment. This
information is used to update the policy using the RL algorithm. The policy
then selects another action for the new observation and keeps on repeating
these steps until the agent finds the optimal policy $\pi^{*}$. The novelty of
our RL solution is that the policy update incorporates the reward shaping
value, which is constructed using the output of VIN-RS.

The CNN of VIN-RS is built using three two-dimensional CNN layers. The input
to CNN is a list of images captured from the environment. CNN accepts graphs,
in contrast to the main RL algorithm where the input can be a state
representation that combines information other than the environment images.
This is similar to the case of MuJoCo environments [25]. The image is passed
to the first conv layer that is responsible for processing the raw image
pixels. The result of the first conv layer is passed to the second one, which
is responsible of producing a reward matrix $\bar{\mathcal{R}}$. This layer
has two channels, one holds the old value function matrix $\bar{\mathcal{V}}$,
and one holds the current rewards. In other words, states are represented as a
two-dimensional grid at each timestep, and each of these states has a reward
value computed using the first layer. This layer is trained and improved over
time by the network through continuous weights updates. The kernel applied to
this layer resembles the probability transition matrix $\bar{\mathcal{P}}$,
which is also updated during the training. Applying this kernel to the first
reward matrix resulted from the first conv layer will give us the state-action
value function ($\bar{\mathcal{Q}}$-value). At this conv layer, there are $x$
channels, where $x$ is the number of actions in the action space
$\bar{\mathcal{A}}$. Selecting the action having the maximum
$\bar{\mathcal{Q}}$-value is done by applying a max-pooling for the
$\bar{\mathcal{Q}}$ value of the corresponding states. The resulting matrix
$\bar{\mathcal{V}}$ is passed to $\bar{\mathcal{R}}$ to be considered for the
next value iteration or policy update. Furthermore, the $\bar{\mathcal{Q}}$ is
flattened and a dense layer is applied to obtain the output layer. This output
layer has the size of $x$, which is considered as a shaping value for each
action, passed to the main policy update of the RL algorithm to update the
policy using potential-based reward shaping. Producing a shaping value for
each action of a given state is at the core of the look-ahead advice mechanism
[28].

In order to train our CNN, we use the standard backpropagation by computing
the labels using the message passing technique. As discussed in the background
section, the message passing value including the forward and backward messages
is considered as a signal that could accelerate learning. In order to compute
the messages values, a graph of states is formed as shown in Fig. 3, this
graph contains only a subset of the states. Due to the fact that computing
message passing is computationally expensive for large graphs, it is enough to
compute this message passing for the sampled graph of states for the current
training iteration of CNN. For every training episode, the graph is emptied
and a new one is formed. The output of the message passing algorithm is used
as the true labels for the CNN to compute the loss function. In [10], message
passing is implemented using a GCN; however, in this work, we overcome the
limitations of using GCN, described in Section 2.3, and apply CNN to perform
value iteration and compute the message passing values. Because CNN is used to
do planning in the network over $\mathcal{K}$ iterations, VIN-RS can tell if
an agent state belongs to an optimal trajectory. The ability of CNN to plan
using value iteration is mapped to what a message passing value represents.

###  4.2 VIN-RS Module

Figure 3: The CNN architecture of the proposed VIN-RS module

Our VIN-RS builds and solves $\bar{\mathcal{M}}$, where the parameters of the
policy $\bar{\pi}$ include $f_{r}$ and $f_{p}$. These two functions are
differentiable and learned while training the CNN. The CNN is trained using
the message passing result as the label. To obtain $\bar{\pi}^{*}$ for solving
$\bar{\mathcal{M}}$, value iteration is applied as follows:

$\bar{\pi}^{*}(\bar{s})=\text{argmax}_{\bar{a}}\bar{\mathcal{R}}(\bar{s},\bar{a})+\gamma\sum_{\bar{s}^{\prime}}\bar{\mathcal{P}}(\bar{s}^{\prime}|\bar{s},\bar{a})\bar{V}^{*}(\bar{s}^{\prime})$
(3)

where $\bar{s}^{\prime}$ is the state at the next timestep. The value
iteration procedure is implemented using the CNN of the proposed VIN-RS.
Furthermore, we construct a VIN-RS tailored for reward shaping in the context
of RL. Mainly, we train VIN-RS using the message passing values and consider
its output as the shaping value that is used to update the original policy of
the RL algorithm. An illustarion on the training and integration between the
CNN of VIN-RS and the RL module is shown in Figure 2. In addition, the CNN in
VIN-RS is trained in a separate network to solve its own policy and not
combined with the RL network. As shown in Figure 3, the input to CNN is the
list of images extracted from the environment. The input can also be a graph
representation of the states from the environment, in case images are not
available. Using graphs instead of images can reduce the number of states the
CNN trains on; however, it makes our solution applicable to high dimensional
state spaces. In other words, using grid of pixels is practical when the
environment image is two-dimensional or covers the current state and end goal.
Using $f_{r}$, which corresponds to the weights of the first conv layer, the
$\bar{\mathcal{R}}$ matrix is computed. $\bar{\mathcal{R}}$ has the dimension
of $l,m,n$, where $l$ is number of channels and $m$ and $n$ represent the
image dimensions. The extracted reward $\bar{\mathcal{R}}$ is passed to the
next conv layer, where the $\bar{\mathcal{Q}}$ values are computed. The
$\bar{\mathcal{Q}}$ conv layer contains $x$ channels, or a channel for each
action in $\bar{\mathcal{M}}$.
$\bar{\mathcal{Q}}_{\bar{a},i^{\prime},j^{\prime}}$ represents the
$\bar{\mathcal{Q}}$-value for a state defined at positions between
$i,i^{\prime}$ and $j,j^{\prime}$ respectively for a particular action
$\bar{a}$. $\bar{\mathcal{Q}}_{\bar{a},i^{\prime},j^{\prime}}$ is computed as
follows:

$\bar{\mathcal{Q}}_{\bar{a},i^{\prime},j^{\prime}}=\sum_{l,i,j}W_{l,i,j}^{\bar{a}}\bar{\mathcal{R}}_{l,i^{\prime}-i,j^{\prime}-j}$
(4)

In Equation 4, the reward matrix is multiplied by the weights or a
representation of the transition matrix $\bar{\mathcal{P}}$. From the
resulting $\bar{\mathcal{Q}}$ matrix, we apply max-pooling by selecting the
highest $\bar{\mathcal{Q}}$-value from the list of actions or channels to
obtain $\bar{\mathcal{V}}$. An element in $\bar{\mathcal{V}}$ at $i,j$ is:

$\bar{\mathcal{V}}_{i,j}=\text{max}_{\bar{a}}\bar{\mathcal{Q}}(\bar{a},i,j)$
(5)

where $\bar{\mathcal{Q}}(\bar{a},i,j)$ is the result of the
$\bar{\mathcal{Q}}$ function for a given state and action. Following the
computation of $\bar{\mathcal{V}}$, we update the first channel of the
$\bar{\mathcal{R}}$ matrix. In addition, a dense layer is applied after
flattening $\bar{\mathcal{Q}}$. Finally, a fully connected output layer is
added, which results in the shaping values for each action. In order to obtain
the true labels for the shaping value, we apply the message passing mechanism
on the extracted graph from the observations, and pass this value to the loss
of CNN. A forward pass in this CNN is considered as a single value iteration.
Assuming that the number of steps required by the agent to reach the goal from
the current state is $\mathcal{K}$, then the ideal number of value iterations
required in CNN for value function updates is $\mathcal{K}$. After each
iteration, $\bar{\mathcal{V}}$ is calculated using $\bar{\mathcal{Q}}$ and
appended to $\bar{\mathcal{R}}$ for the next iteration, as shown in Figure 3.
In Algorithm 1, we show a pseudo-code of the training steps in our proposed
CNN.

Algorithm 1 A training step with $\mathcal{K}$ value iterations of CNN in VIN-
RS

Input: $X$: a list of images sampled from the environment.

$\mathcal{G}$: a graph constructured from the sampled images or the list of
states encountered.

$cnnH$: Conv layer that processes the image pixels

$cnnR$: Conv layer that computes the $\bar{\mathcal{R}}$ matrix

$cnnQ$: Conv layer that computes the $\bar{\mathcal{Q}}$ matrix

$wV$: Initialize weights for computing $\bar{\mathcal{Q}}$ matrix

$Fn$: Fully connected layer

$Opt$: Output layer

Output: $\phi$: shaping value for the corresponding images/states.

1:$p=\text{Normalize}(X)$ $\triangleright$ or $G$ as input when applicable

2:$h=cnnH(p)$

3:$r=cnnR(h)$

4:$q=cnnQ(r)$

5:$v=\text{Max}(q)$ $\triangleright$ Get the maximum or apply max pooling

6:for $i=1,\dots\mathcal{K}$ do $\triangleright$ Perform $\mathcal{K}$ value
iterations

7: $q=\text{EVALUATE\\_Q}(r,v)$

8: $v=\text{Max}(q)$

9:end for

10:$q=\text{EVALUATE\\_Q}(r,v)$

11:$v=\text{Max}(q)$

12:$flatten\\_q=\text{Reshape}(q)$ $\triangleright$ Flatten the matrix v

13:$fn=Fn(flatten\\_q)$

14:$\phi=Opt(fn)$

15:$label=\text{Message\\_Passing}(\mathcal{G})$

16:$loss=\mathcal{L}(label,\phi)$

17:$backpropagate()$

18:$update\\_gradient()$

19:procedure evaluate_q($(r,v,cnnQ,wV)$) $\triangleright$ Perform value
iteration

20: $rv=\text{Concat}(r,v)$ $\triangleright$ Concatenate $r$ and $v$

21: $wQwV=\text{Concat}(cnnQ\text{.weights},wV)$

22: $q=Conv(rv,wQwV)$ $\triangleright$ Apply a Convolutional layer

23: $\text{return }q$

24:end procedure

The pseudo-code of Algorithm 1 presents how the CNN of VIN-RS is trained for a
single step. Lines 1-5 perform a forward pass in the algorithm. Lines 6-10
perform $\mathcal{K}$ value iterations. Lines 11-13 flatten the
$\bar{\mathcal{Q}}$ matrix and obtain the output $\phi$. Lines 14-15 compute
the message passing values and compute the loss. Line 16 performs
backpropagation to compute the gradients of the network weights. Line 17
updates the weights based on the computed gradient.

###  4.3 Loss Function: Message passing

Following the success of using message passing for reward shaping, we propose
training the CNN of VIN-RS using the message passing values as the true
labels. Using the probability inference view of RL, a solution is to find the
distribution of the optimality variable $\mathcal{O}=1$ for a given state and
action. This structure is analogous to HMM, where forward and backward
messages can be used to compute this probability distribution. Combining the
forward and backward messages results in a policy that looks backward and
forward in time. In other words, the resulting values from message passing
tells if a state belongs to an optimal trajectory. More details about the
messages calculation is presented in Section 3.4. Thus, the combined forward
and backward messages ($\alpha$ and $\beta$) are expressed as follows:

$p(O_{t}|{S}_{t},A_{t})\simeq\alpha(S_{t},A_{t})\beta(S_{t},A_{t})$ (6)

Thus, the potential function is expressed as
$\phi_{\alpha,\beta}=\alpha(S_{t},A_{t})\times\beta(S_{t},A_{t})$. Compared to
VIN, a CNN can also produce optimal plans/trajectories for the agent on
$\bar{\mathcal{M}}$. Based on this observation, we propose VIN-RS that
incorporates the message passing results in the training process to produce
the shaping values.

In VIN-RS, we benefit from message passing to compute the loss of CNN. To
compute those messages, base and recursive losses are required. In our loss
formulation, the state and action are passed as input when computing the loss.
Such formulation boosts the performance of VIN-RS by applying the look-ahead
advice naturally in the CNN implementation, due to the fact that each channel
in $\bar{\mathcal{Q}}$ is a Q-function for each action in the environment.
Therefore, the loss function is computed in two steps as follows:

$\mathcal{L}=\mathcal{L}_{0}(\bar{\mathbf{S}},\bar{\mathbf{A}})+\eta\mathcal{L}_{rec}(\bar{\mathcal{S}},\bar{\mathcal{A}})$
(7)

where $\mathcal{L}_{0}$ is the base case, $\mathcal{L}_{rec}$ is the recursive
case, $\bar{\mathbf{S}}$ and $\bar{\mathbf{A}}$ are the lists of base case
states and actions respectively in $\bar{\mathcal{M}}$, and
$\bar{\mathcal{S}}$ and $\bar{\mathcal{A}}$ are the states and actions
retrieved from the graph of experiences. Noting that the base states are
composed of the rewarding states. In VIN-RS, we consider states that are used
to form the graph $\mathcal{G}$, where each state in this graph is an images
of the environment. Furthermore, the base loss is computed using the rewarding
states only in $\mathcal{G}$, in order to extract information only from
important states. The base loss is the usual supervised loss that considers
the true and predicted labels.

$\displaystyle\mathcal{L}_{0}=H(p(\bar{O}|\bar{\mathbf{S}},\bar{\mathbf{A}}),\phi(\bar{\mathbf{S}},\bar{\mathbf{A}}))=$
(8)
$\displaystyle\sum_{s,a\in\bar{\mathbf{S}},\bar{\mathbf{A}}}p(\bar{O}|s,a)\text{log}(\phi(s,a))$

The recursive loss written as $\mathcal{L}_{rec}$ is computed by aggregating
the messages with the neighboring states using the adjacency matrix of the
graph $\mathcal{G}$. $\mathcal{L}_{rec}$ is formulated as follows:

$\mathcal{L}_{rec}=\sum_{i=1}^{||d||}\sum_{j=1}^{||e||}\mathfrak{A}_{i,j}||\phi(\bar{\mathcal{S}}_{i},\bar{\mathcal{A}}_{i})-\phi(\bar{\mathcal{S}}_{j},\bar{\mathcal{A}}_{j})||^{2}$
(9)

In Equation 9, $d$ and $e$ are the list of states and corresponding neighbors
respectively. In addition, $\mathfrak{A}$ is the adjacency matrix. Getting
$\phi$ for a given state and action is at the output layer $Opt$ of CNN for
VIN-RS. Compared to [10], our loss function considers both the states and
actions for activating the look-ahead advice mechanism.

###  4.4 Look-Ahead Advice

The Look-ahead advice mechanism proposed in [28] suggests considering the
action as part of the potential-based reward shaping function. Advising on
specific actions is a more rigorous method taken at the level of actions
instead of being general for the whole state. The shaping function produced by
CNN in VIN-RS after applying the look-ahead advice takes the following form:

$F(\bar{s},\bar{a},\bar{s}^{\prime},\bar{a}^{\prime})=\gamma\phi(\bar{s}^{\prime},\bar{a}^{\prime})-\phi(\bar{s},\bar{a})$
(10)

where $\phi$ is the potential shaping function that considers states from
$\mathcal{S}$ and actions from $\mathcal{A}$ to result in a scalar value.
Hence, the updated shaping function considering the action taken becomes:

$R(s,a,s^{\prime},a^{\prime})=r(s,a)+F(s,a,s^{\prime},a^{\prime})$ (11)

By augmenting the action values, the shaping function could potentially speed
the learning speed further. Therefore, we propose adding the look-ahead advice
in the design of VIN-RS, which is naturally embedded at the
$\bar{\mathcal{Q}}$ layer.

###  4.5 Training RL with VIN-RS

VIN-RS is able to produce shaping values that can accelerate learning and
overcome the limitation of existing solutions by processing full images of the
environment or extracted graphs of states. After training the CNN of VIN-RS,
the resulting shaping values for each state and action are passed to the RL
algorithm for training and policy update. In Algorithm 2, we show the steps
followed to train RL and benefit from the shaping value to obtain the
$\mathcal{Q}_{comb}$, which is a combination of the original $\mathcal{Q}$
value and the one obtained using Equation 2 with $\phi$ from CNN as the
shaping value. The algorithm starts by initializing the CNN and RL networks,
as well as an empty graph $\mathcal{G}$ to hold the list of transitions. In
each epoch of training, for a number of iterations $T$ (for each trajectory
followed by the agent), images are stored to later train the CNN. In addition,
the list of transitions are stored in graph $\mathcal{G}$ to later compute the
loss of CNN. For every $N$ episodes, the CNN is trained with the sampled
images and graphs of transitions. Training the CNN every $N$ episodes is more
efficient and reduces the runtime of using VIN-RS in combination with the RL
solution to speed learning. The loss is computed using Equation 7 and the CNN
is trained for $\mathcal{K}$ iterations following the steps of Algorithm 1.
Noting that if images are not available for training the CNN, the graph
$\mathcal{G}$ can be used instead.

The combined value function with reward shaping is expressed as:

$\displaystyle\mathcal{Q}_{comb}^{\pi}(s,a)=\alpha\mathcal{Q}^{\pi}(s,a)+(1-\alpha)\bar{\mathcal{Q}}^{\bar{\pi}}_{\phi}(s,a)$
(12) $\displaystyle\text{where
}\bar{\mathcal{Q}}^{\bar{\pi}}_{\phi}(s,a)=\mathbf{E}_{(s,a)}[\sum_{t}\gamma^{t}r(S_{t},A_{t})+\gamma\phi(S_{t+1},$
$\displaystyle A_{t+1})-\phi(S_{t},A_{t})]$

$\phi(S_{t},A_{t})$ is the shaping value at the output layer $Opt$ of the CNN
for state $S_{t}$ and action $A_{t}$. Moreover, $\alpha$ is a hyperparameter
the amount of the reward shaping value considered for updating the state-
action value function. At the end of an epoch, the graph $\mathcal{G}$ can be
emptied.

Algorithm 2 Training RL with VIN-RS

1:Create the CNN network for VIN-RS

2:Create empty graph $\mathcal{G}$

3:Create the RL networks

4:for Episode=0,1,2, … do

5: for $t=1,2,\dots,T$ do

6: Store images of all transitions

7: Perform the best action based on $\pi$

8: Get the state and reward from the environment

9: Add the transition to graph $\mathcal{G}$

10: end for

11: if mod(Episode, $N$) then

12: Pass the list of images to CNN

13: Compute the loss for CNN using Equation 7

14: Train CNN following Algorithm 1 for $\mathcal{K}$ iterations

15: end if

16: Obtain $\phi$ for the list of states and actions

17:
$\mathcal{Q}_{comb}^{\pi}=\alpha\mathcal{Q}^{\pi}+(1-\alpha)\bar{\mathcal{Q}}^{\bar{\pi}}_{\phi}$

18: Train RL networks by updating the policy to maximize $E_{\pi}[\nabla
log\pi(A_{t}|S_{t})\mathcal{Q}_{comb}^{\pi}(S_{t},A_{t})]$

19: Reset $\mathcal{G}$ to empty graph (optional)

20:end for

##  5 Experiments

In this section, the evaluation consists of experiments on two environments
with discrete and continuous state and control. We use twenty Atari 2600 games
from the Gym environment and four games from MuJoCo. In order to analyse the
performance of VIN-RS and illustrate its advantage, we compare with the
Proximal Policy Optimization (PPO) [22]; using GCN (denoted as $\phi_{GCN}$)
as the shaping function with the graph Laplacian as the filter [10]; LIRPG
[30]; RND [4]; and ICM [16]. Details about the implementation and machines
used are provided in the next subsection. First, we analyze the time
complexity of VIN-RS compared to PPO and GCN. Afterward, we evaluate the
performance of VIN-RS in different games for the Atari 2600 [3], and MuJoCo
[25] environments compared to various baselines.

###  5.1 Implementation and Setup

The source code is written in the Python programming language. In our
implementation, we used the PyTorch library to build our VIN-RS and combine it
with the implementation of the Actor Critic (A2C) and Proximal Policy
Optimization (PPO) algorithm. We also utilize the OpanAi Gym [3] and MuJoCo
[25] libraries to simulate the environments of all the games. Images are
passed to CNN to train in both the Atari and MuJoCo environments. The state
representation of the MuJoCo games contains additional information about the
state and not only the raw pixels. Therefore, we utilized the camera option in
the MuJoCo package to build the CNN input. In case there is no option to get
images from the environment, a graph of states can be used as input to CNN.
The same graph of states is used to compute the loss function, through message
passing, when training the CNN. Passing images as input results in more
information about the environment, which further improves the performance of
CNN. As described in Section 4, the look-ahead advice mechanism is naturally
embedded within the VIN-RS design and implementation, which offers a level of
advantage for the proposed scheme compared to existing baselines. Our source
code is available on GitHub and will be shared after publication.

For each run, a single GPU (NVIDIA V100 Volta (16GB HBM2 memory)) and eight
CPUs (Intel E5-2683 v4 Broadwell @ 2.1GHz) were used with 32 GB of RAM.
Details about the network configuration of each environment are provided in
Sections 5.3.2 and 5.3.3.

###  5.2 Complexity

In this section, we show the results of our analysis in terms of runtime of
the proposed VIN-RS when combined with PPO compared to GCN and vanilla PPO. In
Table 1, we show the number of frames processed per second (FPS) using each of
the solutions. As presented in Algorithm 1, the CNN of VIN-RS is only trained
every $N$ episodes, that’s why the FPS is very close compared to the other
solutions. Therefore, when comparing the performance of VIN-RS to the other
baselines, it is enough to compare the cumulative steps to converge or the
average reward achieved over the number of iterations.

Method | FPS
---|---
PPO | 1126
GCN | 1054
VIN-RS | 1051
Table 1: Frame Per Second (FPS) evaluated on Atari 2600

Training VIN-RS consumes additional time every couple of episodes due to the
added computation of the loss using Equation 7, in addition to the steps of
training CNN following Algorithm 1. Therefore, VIN-RS has comparable execution
time compared to PPO and GCN, thus not affecting the speed of learning. Hence,
studying the number of iterations to convergence has the same effect as
measuring the time in seconds when comparing to different baselines in the
following subsections.

###  5.3 Performance Analysis

In our evaluations, we consider three different environments to test the
performance of the proposed VIN-RS. First is the Tabular with the four rooms
game, second is the Atari 2600, and third is the MuJoCo. All these
environments are similar to the evaluation criteria followed in [10] that
proposes the use of GCN to perform message passing and predict the shaping
value. Even-though the $\phi_{CNN}$ (using VIN-RS) approach for reward shaping
achieves considerable improvement over the PPO algorithm in [10], we still
provide a comparison with A2C and PPO as baselines.

####  5.3.1 Tabular Learning

In this experiment, we present two setups of the Four Rooms game to evaluate
the performance of VIN-RS $\phi_{CNN}$ that uses A2C. The analysis conducted
on VIN-RS is compared to A2C, $\phi_{GCN}$, and $\phi_{\alpha\beta}$. In
$\phi_{\alpha\beta}$, message passing is computed due to the small environment
spaces. Furthermore, $\lambda$-return is used as the critic part of A2C. A
tabular RL solution is enough for the four rooms game shown in Figure 4(a). In
such an environment, it is possible to compute the actual message passing
value $\phi_{\alpha\beta}$. However, in larger environment sizes and
dimensions, it is not feasible to compute those messages. The two games we
evaluate are the Four Rooms and its variant Four Rooms Traps, where negative
rewards are scattered across the four rooms as traps. Moreover, the
exploration rate is maintained by setting the probability of random action
selection to 0.1. The results showing the cumulative steps are presented in
Figures 4 and 5.

(a) Four Rooms

(b) Convergence Speed

Figure 4: Cumulative steps over the number of iterations in Four Rooms

(a) Four Rooms Traps

(b) Convergence speed

Figure 5: Cumulative steps over the number of iterations in Four Rooms Traps

As shown in Figure 4, $\phi_{CNN}$ has faster convergence speed indicated by
less number of cumulative steps compared to A2C, $\phi_{\alpha\beta}$, and
$\phi_{GCN}$. In particular, after 300 episodes, $\phi_{CNN}$ In this
particular game, VIN-RS helps the agent plan the optimum trajectory by
selecting the shortest path to reach the goal with a smaller number of
training iterations. The planning factor is not possible when using message
passing through GCN as the potential function, because (1) a subset of the
states is only considered when training, and (2) value iteration is not
performed to ensure planning.

####  5.3.2 Atari 2600

The Gym library offers environments for twenty different Atari 2600 games. The
main property of these games is that the action space is discrete. In this
section, we evaluate the performance of our proposed solution $\phi_{CNN}$ in
each of the games compared to four baselines, which are PPO, $\phi_{GCN}$,
LIRPG, RND, and ICM. In terms of VIN-RS implementation, we use the states
which are raw pixel representation as input to the CNN. Furthermore, the
number of channels at the $\bar{\mathcal{Q}}$ layer is equal to the number of
actions of the game.

We experiment with the twenty different Atari 2600 games using $\phi_{CNN}$,
$\phi_{GCN}$, LIRPG, RND, ICM, and PPO. We execute each algorithm on every
game for ten million steps, the same parameters are used as shown in Table 2.

Table 2: VIN-RS and RL configuration for the Atari 2600 games Hyperparameter | Value
---|---
Learning rate | 2.5e-4
$\gamma$ | 0.99
$\lambda$ | 0.95
Entropy Coefficient | 0.01
PPO steps | 128
PPO Clipping Value | 0.1
# of minibatches | 4
# of processes | 8
CNN: $\alpha$ | 0.9
CNN: $\eta$ | 1e1
GCN: $\alpha$ | 0.9
GCN: $\eta$ | 1e1

In Figure 6(a), we show the improvement achieved by $\phi_{CNN}$ using VIN-RS
over PPO. In addition, we present the improvement of each of the baselines
$\phi_{GCN}$, LIRPG, RND, and ICM compared to PPO in Figures 6(b), 6(c), 6(d),
and 6(e) respectively. The results in these figures are shown in logarithmic
scale. The mean difference between each solution and PPO is computed, then a
log is applied.

(a) $\phi_{CNN}$

(b) $\phi_{GCN}$

(c) LIRPG

(d) RND

(e) ICM

Figure 6: Performance comparison of each learning and reward shaping algorithm
on Atari games in log scale over ppo

As shown in Figure 6(a), the proposed $\phi_{CNN}$ is able to improve the
performance of 14 different Atari games compared to PPO as a baseline. In the
games of Venture, Qbert, UpNDown, MsPacman, and SpaceInvaders, $\phi_{CNN}$ is
not performing well compared to PPO. In contrast, the performance of
$\phi_{GCN}$ in this game is better compared to PPO. On the other hand, in
most of the other games, $\phi_{CNN}$ is outperforming $\phi_{GCN}$ and
improving over PPO. These information are extracted from Figures 6(a) and
6(b). Furthermore, the proposed $\phi_{CNN}$ has the best results in terms of
the number of games where the performance is better than PPO compared to the
rest of the baselines. More specifically, the number of games with an
improvement of PPO are classified as $\phi_{CNN}$: 13, $\phi_{GCN}:9$, LIRPG:
11, RND: 7, ICM: 12.

These results highlight the capabilities of performing value iteration or
message passing using the proposed CNN architecture. Compared to $\phi_{CNN}$,
LIRPG does not guarantee invariance for the optimal policy, thus it is not
potential-based. On the other hand, RND and ICM provide reward shaping through
exploration and can only support discrete action spaces. Additional results
showing the performance comparison between $\phi_{CNN}$, $\phi_{GCN}$, and PPO
are presented in Figure 7.

(a) Alien

(b) Assault

(c) Asteroids

(d) Frosbite

(e) Gopher

(f) Jamesbond

(g) Hero

(h) Kangaroo

(i) Krull

(j) MontezumaRevenge

(k) MsPacman

(l) NameThisGame

(m) Qbert

(n) RoadRunner

(o) Seaquest

(p) SpaceInvaders

(q) UpNDown

(r) Venture

(s) WizardOfWar

(t) Zaxxon

Figure 7: Results on 20 Atari games comapring the performance of $\phi_{CNN}$
to $\phi_{GCN}$ and PPO

####  5.3.3 Mujoco

We evaluate the performance of VIN-RS in continuous action space on the MuJoco
games compared to baselines. In the CNN implementation of VIN-RS, we deal with
the continuous action space by discretizing the action space. The values of
two actions at the output layer resemble the range of the continuous actions
in $\mathcal{M}$. The rest of the implementation is similar to the Atari
games. In terms of baselines comparison, we compare with PPO and $\phi_{GCN}$.
It is not possible to compare with RND and ICM because these solutions do not
support continuous control. We only compare with $\phi_{GCN}$ as a reward
shaping solution because it is the closest to our work in terms of potential-
based solution and the use of message passing. The results comparing the
performance of each game to the other baselines are shown in Figure 8. The
different settings related to this experiment are provided in Table 3. We use
the same parameters as in [10] for evaluating the different techniques and
baselines for fair comparison. The experiments were executed for three million
steps for each game. We performed the experiment for each solution on each
game for five times. The results in Figure 8 show the mean for each of the
games in terms of rewards with respect to the number of steps in the
environment.

Table 3: VIN-RS and RL configurations for the MuJoCo games Hyperparameter | Value
---|---
Learning rate | 3e-4
$\gamma$ | 0.99
$\lambda$ | 0.95
Entropy Coefficient | 0.0
PPO steps | 2048
PPO Clipping Value | 0.1
# of minibatches | 32
# of processes | 1
CNN/GCN (Walker and Ant): $\alpha$ | 0.6
CNN/GCN (Hopper and HalfCheetah): $\alpha$ | 0.6
CNN/GCN: $\eta$ | 1e1

(a) Ant

(b) HalfCheetah

(c) Hopper

(d) Walker2d

Figure 8: Performance comparison between different reward shaping mechanisms
and PPO in Mujoco environments.

As shown in the results of Figure 8, the proposed $\phi_{CNN}$ solution using
VIN-RS outperforms PPO and $\phi_{GCN}$ in all the MuJoCo games. This
improvement is measured by the convergence speed and the ability to reach high
rewards at early stages of learning. In addition, the planning capability of
$\phi_{CNN}$ is reflected in the performance by reaching high rewards that are
not observed by the other solutions. In the results of the Hopper game of
Figure 8(c), $\phi_{CNN}$ reaches higher rewards, which is at least two times
better than $\phi_{GCN}$ and PPO.

##  6 Conclusion and Discussion

In this paper, we propose VIN-RS, a potential-based reward shaping mechanism
that employs a novel CNN architecture as a potential function. VIN-RS performs
planning in the environment by implementing a value iteration functionality.
The loss function of CNN for value iteration is computed using the message
passing mechanism that embeds forward and backward messages, resulting in an
effective potential function for rewards shaping. The training of CNN is
performed on a sample of transitions. Our solution embeds the look-ahead
advice mechanism inside the design of CNN for VIN-RS. We then propose the use
of CNN as the potential function to produce shaping values. The resulting
shaping values from sampled trajectories at each action are passed to the RL
algorithm to update the policy. In terms of learning speed, VIN-RS achieves
state-of-the-art results in various games. Besides, through planning, the CNN
for reward shaping can converge faster and reach high rewards that are not
observable by other solutions. In our evaluations, we showed that the
complexity of combining VIN-RS with other RL solutions is minimal.
Furthermore, we evaluated the performance of VIN-RS compared to other
baselines in Tabular, Atari 2600, and MuJoCo environments.

In terms of future work, the current implementation of VIN-RS does not support
high-dimensional state spaces, such as using the MiniWorld environment. This
issue can be solved following the VIN generalization solution proposed in
[14].

Using VIN-RS, we believe that existing RL-based solutions in the studied MDP
environments have the potential to improve the learning speed and quality of
the decisions at the same time. For example, there are various dynamically
changing and time-sensitive MDPs requiring fast adaptation to environmental
changes. Examples of these environments include autonomous driving, resource
management [20, 21], health applications, Blockchain [9, 7], and financial
applications [27].

## References

  * Alagha et al. [2022] Alagha, A., Singh, S., Mizouni, R., Bentahar, J., & Otrok, H. (2022).  Target localization using multi-agent deep reinforcement learning with proximal policy optimization.  Future Generation Computer Systems, 136, 342–357.
  * Amodei et al. [2016] Amodei, D., Olah, C., Steinhardt, J., Christiano, P. F., Schulman, J., & Mané, D. (2016).  Concrete problems in AI safety.  CoRR, abs/1606.06565.
  * Brockman et al. [2016] Brockman, G., Cheung, V., Pettersson, L., Schneider, J., Schulman, J., Tang, J., & Zaremba, W. (2016).  OpenAI Gym.  arXiv preprint arXiv:1606.01540, .
  * Burda et al. [2018] Burda, Y., Edwards, H., Storkey, A., & Klimov, O. (2018).  Exploration by random network distillation.  In ICLR.
  * Garaffa et al. [2021] Garaffa, L. C., Basso, M., Konzen, A. A., & de Freitas, E. P. (2021).  Reinforcement learning for mobile robotics exploration: A survey.  IEEE Transactions on Neural Networks and Learning Systems, . doi:10.1109/TNNLS.2021.3124466.
  * Grześ & Kudenko [2010] Grześ, M., & Kudenko, D. (2010).  Online learning of shaping rewards in reinforcement learning.  Neural Networks, 23, 541–550.
  * Hammoud et al. [2020] Hammoud, A., Sami, H., Mourad, A., Otrok, H., Mizouni, R., & Bentahar, J. (2020).  Ai, blockchain, and vehicular edge computing for smart and secure iov: Challenges and directions.  IEEE Internet of Things Magazine, 3, 68–73.
  * Harutyunyan et al. [2015] Harutyunyan, A., Brys, T., Vrancx, P., & Nowé, A. (2015).  Shaping mario with human advice.  In AAMAS (pp. 1913–1914).
  * Kadadha et al. [2022] Kadadha, M., Otrok, H., Mizouni, R., Singh, S., & Ouali, A. (2022).  On-chain behavior prediction machine learning model for blockchain-based crowdsourcing.  Future Generation Computer Systems, .
  * Klissarov & Precup [2020] Klissarov, M., & Precup, D. (2020).  Reward propagation using graph convolutional networks.  In NeurIPS.
  * Li et al. [2021] Li, W., Yang, B., Song, G., & Jiang, X. (2021).  Dynamic value iteration networks for the planning of rapidly changing UAV swarms.  Frontiers of Information Technology & Electronic Engineering, (pp. 1–10).
  * Mnih et al. [2013] Mnih, V., Kavukcuoglu, K., Silver, D., Graves, A., Antonoglou, I., Wierstra, D., & Riedmiller, M. A. (2013).  Playing Atari with deep reinforcement learning.  CoRR, abs/1312.5602.
  * Ng et al. [1999] Ng, A. Y., Harada, D., & Russell, S. (1999).  Policy invariance under reward transformations: Theory and application to reward shaping.  In ICML (pp. 278–287).
  * Niu et al. [2018] Niu, S., Chen, S., Guo, H., Targonski, C., Smith, M. C., & Kovačević, J. (2018).  Generalized value iteration networks: Life beyond lattices.  In AAAI (pp. 6246–6253).
  * Oh et al. [2020] Oh, J., Hessel, M., Czarnecki, W. M., Xu, Z., van Hasselt, H. P., Singh, S., & Silver, D. (2020).  Discovering reinforcement learning algorithms.  In NeurIPS.
  * Pathak et al. [2017] Pathak, D., Agrawal, P., Efros, A. A., & Darrell, T. (2017).  Curiosity-driven exploration by self-supervised prediction.  In ICML (pp. 2778–2787).
  * Petrik [2007] Petrik, M. (2007).  An analysis of Laplacian methods for value function approximation in MDPs.  In IJCAI (pp. 2574–2579).
  * Rabiner & Juang [1986] Rabiner, L., & Juang, B. (1986).  An introduction to hidden Markov models.  IEEE ASSP Magazine, 3, 4–16.
  * Sami et al. [2022] Sami, H., Bentahar, J., Mourad, A., Otrok, H., & Damiani, E. (2022).  Graph convolutional recurrent networks for reward shaping in reinforcement learning.  Information Sciences, 608, 63–80.
  * Sami et al. [2021a] Sami, H., Mourad, A., Otrok, H., & Bentahar, J. (2021a).  Demand-driven deep reinforcement learning for scalable fog and service placement.  IEEE Transactions on Services Computing, .
  * Sami et al. [2021b] Sami, H., Otrok, H., Bentahar, J., & Mourad, A. (2021b).  Ai-based resource provisioning of ioe services in 6g: A deep reinforcement learning approach.  IEEE Transactions on Network and Service Management, 18, 3527–3540.
  * Schulman et al. [2017] Schulman, J., Wolski, F., Dhariwal, P., Radford, A., & Klimov, O. (2017).  Proximal policy optimization algorithms.  CoRR, abs/1707.06347.
  * Shurrab et al. [2022] Shurrab, M., Singh, S., Mizouni, R., & Otrok, H. (2022).  Iot sensor selection for target localization: A reinforcement learning based approach.  Ad Hoc Networks, 134, 102927.
  * Tamar et al. [2016] Tamar, A., Wu, Y., Thomas, G., Levine, S., & Abbeel, P. (2016).  Value iteration networks.  In NIPS (pp. 2146–2154).
  * Todorov et al. [2012] Todorov, E., Erez, T., & Tassa, Y. (2012).  Mujoco: A physics engine for model-based control.  In 2012 IEEE/RSJ International Conference on Intelligent Robots and Systems (pp. 5026–5033).
  * Toussaint & Storkey [2006] Toussaint, M., & Storkey, A. (2006).  Probabilistic inference for solving discrete and continuous state Markov decision processes.  In ICML (pp. 945–952).
  * Tsantekidis et al. [2020] Tsantekidis, A., Passalis, N., Toufa, A.-S., Saitas-Zarkias, K., Chairistanidis, S., & Tefas, A. (2020).  Price trailing for financial trading using deep reinforcement learning.  IEEE Transactions on Neural Networks and Learning Systems, 32, 2837–2846.
  * Wiewiora et al. [2003] Wiewiora, E., Cottrell, G. W., & Elkan, C. (2003).  Principled methods for advising reinforcement learning agents.  In ICML (pp. 792–799).
  * Yang et al. [2018] Yang, S., Li, J., Wang, J., Liu, Z., & Yang, F. (2018).  Learning urban navigation via value iteration network.  In IEEE Intelligent Vehicles Symposium (IV) (pp. 800–805).
  * Zheng et al. [2018] Zheng, Z., Oh, J., & Singh, S. (2018).  On learning intrinsic rewards for policy gradient methods.  NeurIPS, (pp. 4649–4659).
  * Ziebart et al. [2008] Ziebart, B. D., Maas, A. L., Bagnell, J. A., & Dey, A. K. (2008).  Maximum entropy inverse reinforcement learning.  In AAAI (pp. 1433–1438).


# Cough Detection Using Selected Informative Features from Audio Signals

Xinru Chen  School of Communication
and Electronic Engineering
East China Normal University
<EMAIL_ADDRESS>Menghan Hu  School of Communication
and Electronic Engineering
East China Normal University
<EMAIL_ADDRESS>
*Corresponding author  Guangtao Zhai  Institute of Image Communication
and Network Engineering
Shanghai Jiao Tong University
<EMAIL_ADDRESS>
###### Abstract

Cough is a common symptom of respiratory and lung diseases. Cough detection is
important to prevent, assess and control epidemic, such as COVID-19. This
paper proposes a model to detect cough events from cough audio signals. The
models are trained by the dataset combined ESC-50 dataset with self-recorded
cough recordings. The test dataset contains inpatient cough recordings
collected from inpatients of the respiratory disease department in Ruijin
Hospital. We totally build 15 cough detection models based on different
feature numbers selected by Random Frog, Uninformative Variable Elimination
(UVE), and Variable influence on projection (VIP) algorithms respectively. The
optimal model is based on 20 features selected from Mel Frequency Cepstral
Coefficients (MFCC) features by UVE algorithm and classified with Support
Vector Machine (SVM) linear two-class classifier. The best cough detection
model realizes the accuracy, recall, precision and F1-score with 94.9%, 97.1%,
93.1% and 0.95 respectively. Its excellent performance with fewer
dimensionality of the feature vector shows the potential of being applied to
mobile devices, such as smartphones, thus making cough detection remote and
non-contact.

##  I Introduction

Cough is one of the commonest symptoms of respiratory and lung diseases such
as asthma, pertussis and pneumonia. It is a body mechanism to clear upper
respiratory tract and eject excessive amount of mucus and foreign particles
from respiratory system [1]. The mechanical phases of a cough event include
that the glottis closes after deep inhalation, and the glottis opens while
rapid expiratory flow occurs, producing a specific audio signal [2].

Because cough events convey vital information of the state of the respiratory
system and the status of the disease progression, various cough event
assessment devices have been developed to detect cough events and calculate
cough frequency, cough intensity, cough impact, cough duration and other
indicators [3]. In addition to manual assessment methods such as manual cough
counter, objective cough assessment devices such as the Leicester Cough
Monitor [4], the Hull Automatic Cough Counter [5] and VitaloJak system [6] are
available. Although these objective cough assessment devices can be used as
wearable cough detection systems with high accuracy, they are not suitable for
large-scale cough screening applications.

Cough event detection for a large number of people plays an important role in
epidemic prevention and control, epidemiological research, risk assessment of
infectious diseases and other fields. For example, by July 30 2021, COVID-19,
a global pandemic, has confirmed 196,553,009 cases and caused 4,200,412
deaths, according to World Health Organization (WHO) [7]. Due to the spread of
the mutant COVID-19 coronavirus and the unbalanced vaccine supply, the global
COVID-19 pandemic is facing a severe situation again. In the COVID-19
pandemic, the primary symptom of a patient with COVID-19 coronavirus may be
cough [8]. Therefore, large-scale and contactless cough detecting applications
are of great importance.

The occurrence of cough events is usually accompanied by the production of
some specific sounds. Therefore, many scholars used audio signals to build
models, so as to achieve remote detection of cough events. Alsabek reported
the importance of Mel Frequency Cepstral Coefficients (MFCC) extraction of
COVID-19 and non-COVID-19 samples in cough signal process [9]. Monge-Álvarez
reported that using local Hu moments as a robust feature for cough detection
with audio signals [10]. Al-Khassaweneh used Wigner distribution and wavelet
transform to analyze cough signals for detecting asthma [11]. Pramono
developed an algorithm based on features of the audio signals with a logistic
regression model to identify cough events [12]. Laguarta developed an
Artificial Intelligence (AI) speech processing architecture based on a
Convolutional Neural Network (CNN) to screening the coughing symptom of
COVID-19 [13]. Imran proposed a COVID-19 diagnosis system using the
combination of machine learning and deep learning from cough samples via an
App [14].

Most studies we mentioned above extract a large number of feature and classify
with complex deep learning or machine learning model, which may be infeasible
or time-consuming to apply in remote mobile devices, such as smartphones.
Meanwhile, it may increase the risk of overfitting. Cough detection, a
relatively simple problem, does not require complicated technical solutions to
solve. What’s more, most studies do not include cough samples recorded in
scenarios where cough detection is required such as the ward in their dataset.
Therefore, it is necessary to develop a cough detection model using small
number of features and machine learning algorithm such as Support Vector
Machine (SVM) while achieving optimal performance with inpatient cough
samples.

SVM, a well-known classifier, is widely used in various detection and
identification techniques. Kumar presented a person authentication framework
using SVM classifier to implement person identification and verification [15].
Song proposed a sound-of-tapping technology based on SVM, including 7 tapping
position classification and 6 medium identification [16]. Many studies used
SVM as a classifier to implement cough detection. Bhateja reported a method
for features extraction and classification of cough sound in noisy environment
using SVM [17]. Vhaduri developed a cough and snore detection framework based
on several machine learning classifiers including SVM, which can be
implemented on a smartphone [18].

In this paper, we compare the performance of models using different feature
space optimization methods, including Random Frog, Uninformative Variable
Elimination (UVE) and Variable influence on projection (VIP), and propose the
optimal model of automatic cough detection which uses 20 features selected
from MFCC features by UVE algorithm and classifies with SVM linear two-class
classifier. Our model can achieve 94.9% accuracy of classifying between cough
audios and non-cough audios.

In Section 2, we summarize the methods and the specific process of our cough
detection model. Section 3 explains the dataset we used to train and test our
model, describes the experimental results with performance metrics and
discusses the potential and limitations of our study. Section 4 draws a
conclusion.

##  II Method

###  II-A Feature Extraction and Dimension Reduction

We first extract Mel Frequency Cepstral Coefficients (MFCC) from the cough
audios result in a $5000\times 36$ feature matrix. Then, we take the top few
Principal Component Analysis (PCA) projections of the MFCC features which keep
95% of the main information and combine them into a feature vector with the
dimension of 107. By combining MFCC feature extraction method and PCA, it was
expected to improve the accuracy in automatic speech recognition system and
reduce the feature dimension [19].

####  II-A1 MFCC

For automatic speech recognition, MFCC features have been found to a useful
feature extraction method [19]. The Mel scale describes the nonlinear
characteristics of human ear frequency, and its relationship with frequency
can be approximated by the following equation:

$\operatorname{Mel}(f)=2595\times\lg\left(1+\frac{f}{700}\right)$ (1)

It is aimed to reflect audible changes and conform to the auditory
characteristics of the human ear more closely when making changes in
frequency. Then, the Cepstral analysis is performed on the Mel spectrum of
cough audios to compute their Cepstral coefficients, thus obtaining MFCC
features. The process of MFCC is shown in Fig. 1(a).

(a) MFCC diagram block

(b) PCA diagram block

Figure 1: Diagram block of feature extraction (a) and dimension reduction (b)

####  II-A2 PCA

PCA is a useful dimension reduction method with high correlation level. PCA
processing steps can be seen in Fig. 1(b).

#####

There are $m$ samples with $n$ dimension to form a $n\times m$ matrix $X$.
Decentralize each row of $X$ by subtracting the mean of that row.

#####

Calculate the covariance matrix $C=\frac{1}{m}XX^{\top}$.

#####

Calculate the eigenvalues and corresponding eigenvectors of the covariance
matrix.

#####

Form a feature vector. The eigenvectors are arranged in rows from top to
bottom according to the size of corresponding eigenvalues, and the first $k$
rows are taken to form matrix $P$.

#####

$Y=PX$ is the feature vector after dimensionality reduction to $k$.

###  II-B Feature Space Optimization

To select informative features, reduce the complexity of the model and the
risk of overfitting, and make future practical application more effective at
the same time, we use the following three feature selection algorithms: Random
Frog, UVE algorithm and VIP algorithm.

####  II-B1 Random Frog

Random Frog is an effective feature selection algorithm for high dimensional
feature. It can use a small number of feature iteration for modeling and
output the possibility of each feature selection, which can be used as a
feature selection criterion [20]. Fig. 2 shows the key steps of Random Frog
algorithm. Its main calculation steps include the following three steps:

#####

Given an initial variable subset $V_{0}$ and initialize $V_{0}$ with $Q$
variables.

#####

Based on the initial variable subset $V_{0}$, a candidate variable subset
$V^{*}$, including $Q^{*}$ variables, is proposed. Choose $V^{*}$ as $V_{1}$
instead of the initial variable subset $V_{0}$. Repeat the above process until
$N$ iterations are finished.

#####

Compute the selection probability of each variable and use the selection
probability as the criterion for selecting variables.

Figure 2: Key steps of Random Frog algorithm. $V_{0}$: Variable subset; $Q$:
Number of variable in $V_{0}$; $V^{*}$: Candidate variable subset; $Q^{*}$:
Number of variable in $V^{*}$; $i$: Iterations. (Note: From reference [20].)

Based on the single $107\times 1$ feature vector obtained from PCA, we select
10, 20, 30, 40 and 50 features respectively using Random Frog algorithm.

####  II-B2 UVE Algorithm

UVE is a feature selection algorithm based on a stability analysis of PLS
regression coefficients which can eliminate variables of invalid information
in the PLS regression model, thus improving the speed, anti-interference
ability, and predictive stability of PLS models [21]. UVE algorithm’s main
principle is to add artificial random variables to the original variable
matrix, calculate a selection criterion for original and random variables, and
keep original variables whose selection criterion result is larger than that
of random variables. The selection criterion calculation is the ratio of
regression coefficient $b_{j}$ and its standard deviation
$\boldsymbol{s}\left(b_{j}\right)$, measuring the reliability of the PLS
regression coefficient $c_{j}$ [22].

$c_{j}=b_{j}/s\left(b_{j}\right)\text{ for }j=1,\ldots,p$ (2)

We select 10, 20, 30 and 40 features respectively from the single $107\times
1$ feature vector obtained from PCA using UVE algorithm.

####  II-B3 VIP Algorithm

VIP algorithm is used to screen out the most relevant variables. VIP is a
parameter that calculates the cumulative influence of individual X-variables
in a PLS model. Equation 3 gives a detailed calculation of VIP:

$VIP_{PLS}=\sqrt{K\times\left(\frac{\left[\Sigma_{a=1}^{A}\left(W_{a}^{2}\times
SSY_{\text{comp },a}\right)\right]}{SSY_{\text{cum }}}\right)}$ (3)

where a means PLS dimension, $K$ means the total number of variables,
$W_{a}^{2}$ means the squared PLS weight, and $SS$ means the explained the sum
of squares [23]. The values of VIP above 1 are considered as the most relevant
variables, and the values of VIP smaller than 0.5 express irrelevant
variables. We select top 10, 20, 30, 40 and 50 features whose VIP values are
larger than 1 according to the single $107\times 1$ feature vector obtained
from PCA.

###  II-C Cough and Non-cough Classification

On the basis of the features selected, we use classifiers to classify cough
samples and non-cough samples, thus detecting cough. In the current work, SVM
linear dichotomous classifiers is used for the classification. The basic idea
of SVM is to find the separation hyperplane that can divide the training data
set correctly and maximize the margin between the two classes. SVM constructs
a hyperplane in a high dimensional space which can be used for classification,
and training data samples are referred as points in the high dimensional
space. The points that are nearest to the hyperplane drawn previously are
known as Support Vectors, and the distance between these vectors and the
hyperplane is defined as margin. SVM model attempts to find the optimal
hyperplane with maximum margin distance.

##  III Experiments

###  III-A Dataset Explanation

Our dataset consists of cough samples and non-cough samples. The cough samples
include cough sounds in Environmental Sound Classification (ESC-50) dataset,
self-recorded cough recordings and inpatient cough recordings from the
patients with respiratory diseases. The non-cough samples are chosen from
labeled environmental recordings in ESC-50 dataset, including animal sounds,
natural sounds, human (non-speech) sounds, interior sounds and other exterior
noises [24]. The inpatient cough recordings are collected from inpatients of
the respiratory disease department in Ruijin Hospital. The inpatients we
recorded suffered from respiratory disease and had symptoms of cough. The
cough samples collected were recorded by mobile microphone, and background
noise is included in these cough samples. The duration of every sample in our
dataset is 5 seconds.

(a) 40 features selected by Random Frog

(b) 20 features selected by UVE algorithm

(c) 10 features selected by VIP algorithm

Figure 3: Importance of features from three feature selection algorithms (left
column) and Differences between feature value of a typical cough audio and a
non-cough audio (right column)

Finally, we obtained 335 cough samples and 335 non-cough samples, a total of
670 samples. In the classification process, we separate our dataset into
training dataset and testing dataset. The training dataset contains 266 cough
samples and 266 non-cough samples.The test dataset includes 69 cough samples
and 69 non-cough samples. All the cough samples in the test dataset are
inpatient cough recordings collected from inpatients with respiratory
diseases.

###  III-B Informative Features Selection

We choose the best model for each feature selection algorithm introduced in
Section 2 and draw the importance of features in Fig. 3 (left column). The
importance of features from Random Frog, UVE and VIP is respectively described
as selection probability, PLS regression coefficient and variable influence on
projection. The features with importance above the cut-off threshold drawn in
Fig. 3 (left column) are chosen as informative features. Fig. 3 (right column)
depicts the feature value of a typical cough audio and a typical non-cough
audio after PCA processing. The informative features selected by three feature
selection algorithms are respectively marked with green dots in the right
column of Fig. 3 (a-c). In addition, Fig. 3 (right column) shows the
differences between feature value of the cough audio and the non-cough audio
with red dotted lines, indicating that the selected informative features are
more effective for classification than the original features. Six features
overlap in three models shown in Fig. 3 (right column) despite using different
feature selection algorithms, which means three algorithms can select audio
features informative to cough.

Table 2 : Performance metrics for different feature selection methods. (The
bold rows are the top five performing models. The row with gray background

is the best performing model.)

Feature selection method | Feature number | Accuracy (%) | Sensitivity/Recall (%) | Precision (%) | F1-Score
---|---|---|---|---|---
PCA | 107 | 85.51 | 100 | 77.53 | 0.87
| 10 | 67.39 | 100 | 60.53 | 0.75
| 20 | 79.71 | 100 | 71.13 | 0.83
| 30 | 85.51 | 100 | 77.53 | 0.87
| 40 | 86.23 | 100 | 78.41 | 0.88
Random Frog | 50 | 81.16 | 100 | 72.63 | 0.84
| 10 | 28.99 | 7.25 | 12.82 | 0.09
| 20 | 94.93 | 97.1 | 93.06 | 0.95
| 30 | 94.20 | 95.65 | 92.96 | 0.94
UVE | 40 | 92.03 | 97.1 | 88.16 | 0.92
| 10 | 90.58 | 100 | 84.15 | 0.91
| 20 | 87.68 | 100 | 80.23 | 0.89
| 30 | 84.06 | 100 | 75.82 | 0.86
| 40 | 85.51 | 100 | 77.53 | 0.87
VIP | 50 | 75.36 | 100 | 66.99 | 0.80

###  III-C Classification Result

Table 1 : Confusion matrix for cough detection.

|  | Predicted Class
---|---|---
|  | Cough | Non-cough
True Class | Cough | True Positive(TP) | False Negative(FN)
Non-cough | False Positive(FP) | True Negative(TN)

To evaluate the performance of models, we use the confusion matrix in Table 1
and calculate the performance metrics of accuracy, precision,
sensitivity/recall, and F1-score on the test dataset.

$\text{ accuracy }=\frac{TP+TN}{TP+TN+FP+FN}$ (4) $\text{ precision
}=\frac{TP}{TP+FP}$ (5) $\text{ sensitivity/recall }=\frac{TP}{TP+FN}$ (6)
$\text{ F1-score }=2*\left(\frac{\text{ precision }\times\text{ recall
}}{\text{ precision }+\text{ recall }}\right)$ (7)

We first use the single $107\times 1$ feature vector obtained from the
dimension reduction of PCA to train SVM classifier. Then, we respectively use
10, 20, 30, 40 and 50 features selected by Random Frog, UVE and VIP. We
totally build 15 cough detection models and evaluate their performance of
detecting cough events via the test dataset. The classification results of
these models are presented in Table 2.

According to the results in Table 2, we can see that the model with 20
features selected by UVE algorithm can achieve the best performance, allowing
classification with accuracy, recall, precision and F1-score of 94.9%, 97.1%,
93.1%, and 0.95, respectively. The results indicate that our cough detection
model can reach 94.9% accuracy of classifying between cough event and non-
cough event and use fewer dimensionality of the feature vector.

###  III-D Discussion

The model with 20 features selected by UVE algorithm shows that the
classification performance can be optimized while reducing dimension of the
feature vector. Our model has low complexity, so it is well suited for
deployment at the edge such as smartphones. In addition, the use of audio
combined with our low-complexity model minimizes the computational resources
at the edge. Therefore, it is ideal for long-term deployment in public places
such as wards and subways to monitor the frequency of coughs and thus
providing decision support for inspection and quarantine.

The performance of our cough detection model is limited by the following
factors:

##### Inadequate ambient noise of the training samples

The training samples we used were recorded in a quiet environment using a
stationary mobile microphone, while the test samples have ambient noise. We
will try recording cough and non-cough samples in a more noisy and less
controlled environment and changing the microphone position during recording,
which is more consistent with the actual cough detection applied to mobile
devices.

##### Quantity of the training and test samples

Our cough dataset is not so big enough. In the ongoing work, we will enlarge
our cough recording dataset and combine deep learning algorithm to optimize
our cough detection model.

##### Extraction method of features

Our model only uses selected MFCC features. In the future work, we can combine
MFCC with LPC coefficient and spectral features, such as spectral flatness and
spectral centroid.

##  IV Conclusion

We have developed a cough detection model using SVM classifier and selected
informative features. To train our model, we have used a cough and non-cough
dataset combined ESC-50 dataset with cough samples recorded from people around
our authors using mobile microphone. The test dataset we used is inpatient
cough recordings collected from inpatients of the respiratory disease
department in Ruijin Hospital, who had symptoms of cough. We first extract
MFCC features from the audios in dataset, take the top PCA projections of the
MFCC features to reduce dimension, and combine them into a single $107\times
1$ feature vector. Then, we use three feature selection algorithms, namely
Random Frog, UVE, and VIP, and build several models with different numbers of
features. Finally, we use SVM linear two-class classifier to classify cough
samples and non-cough samples. We have found that the model with 20 features
selected by UVE algorithm can achieve the best model performance with 94.9%
accuracy, 97.1% recall, 93.1% precision and the F1-score of 0.95,
respectively.

In the future work, we will enlarge our dataset, make our model more noise-
proof and improve the performance of our models. We will also try to implement
our cough detection model on customers’ smartphones via an App.

## Acknowledgment

This work is sponsored by the National Natural Science Foundation of China
(No. 61831015, No. 61901172) , the Shanghai Sailing Program (No. 19YF1414100),
and the Science and Technology Commission of Shanghai Municipality (No.
19511120100, No. 18DZ2270700, No. 18DZ2270800).

## References

  * [1] K. F. Chung and I. D. Pavord, “Prevalence, pathogenesis, and causes of chronic cough.” _Lancet_ , vol. 371, no. 9621, pp. 1364–1374, 2008.
  * [2] McCool, F., and Dennis, “Global physiology and pathophysiology of cough: Accp evidence-based clinical practice guidelines.” _CHEST_ , vol. 129, no. 1 Suppl, pp. 48S–53S, 2006.
  * [3] P. Cho, S. S. Birring, H. V. Fletcher, and R. D. Turner, “Methods of cough assessment,” _Journal of Allergy and Clinical Immunology in Practice_ , 2019\.
  * [4] S. S. Birring, T. Fleming, S. Matos, A. A. Raj, D. H. Evans, and I. D. Pavord, “The leicester cough monitor: preliminary validation of an automated cough detection system in chronic cough.” _European Respiratory Journal_ , vol. 31, no. 5, pp. 1013–1018, 2008.
  * [5] S. J. Barry, A. D. Dane, A. H. Morice, and A. D. Walmsley, “The automatic recognition and counting of cough,” _Cough_ , vol. 2, no. 1, p. 8, 2006.
  * [6] K. Mcguinness, A. Kelsall, J. Lowe, A. Woodcock, and J. Smith, “Automated cough detection: A novel approach,” _Am J Respir Crit Care Med_ , vol. 175, p. A381, 01 2007.
  * [7] WHO Coronavirus (COVID-19) Dashboard. [Online]. Available: {https://covid19.who.int/}
  * [8] D. Wang, B. Hu, C. Hu, F. Zhu, X. Liu, J. Zhang, B. Wang, H. Xiang, Z. Cheng, Y. Xiong, Y. Zhao, Y. Li, X. Wang, and Z. Peng, “Clinical characteristics of 138 hospitalized patients with 2019 novel coronavirus–infected pneumonia in wuhan, china,” _JAMA_ , vol. 323, 02 2020.
  * [9] M. Bader, I. Shahin, and A. Hassan, “Studying the similarity of covid-19 sounds based on correlation analysis of mfcc,” 2020.
  * [10] J. Monge, C. Hoyos Barcelo, P. Lesso, and P. Casaseca-de-la Higuera, “Robust detection of audio-cough events using local hu moments,” _IEEE Journal of Biomedical and Health Informatics_ , vol. PP, pp. 1–1, 02 2018.
  * [11] M. Alkhassaweneh and R. Abdelrahman, “A signal processing approach for the diagnosis of asthma from cough sounds,” _Journal of medical engineering and technology_ , vol. 37, pp. 165–71, 04 2013.
  * [12] R. Pramono, A. Imtiaz, and E. Rodriguez-Villegas, “Automatic identification of cough events from acoustic signals,” in _2019 41st Annual International Conference of the IEEE Engineering in Medicine and Biology Society (EMBC)_ , vol. 2019, 07 2019, pp. 217–220.
  * [13] J. Laguarta, F. Hueto, and B. Subirana, “Covid-19 artificial intelligence diagnosis using only cough recordings,” _IEEE Open Journal of Engineering in Medicine and Biology_ , vol. 1, pp. 275–281, 2020.
  * [14] A. Imran, I. Posokhova, H. Qureshi, U. Masood, M. Riaz, K. Ali, C. John, I. Hussain, and M. Nabeel, “Ai4covid-19: Ai enabled preliminary diagnosis for covid-19 from cough samples via an app,” _Informatics in Medicine Unlocked_ , vol. 20, p. 100378, 06 2020.
  * [15] P. Kumar, A. Singhal, R. Saini, P. P. Roy, and D. P. Dogra, “A pervasive electroencephalography-based person authentication system for cloud environment,” _Displays_ , vol. 55, pp. 64–70, 2018, advances in Smart Content-Oriented Display Technology.
  * [16] S.-J. Song and H. Nam, “Sound-of-tapping user interface technology with medium identification,” _Displays_ , vol. 53, pp. 54–64, 2018.
  * [17] V. Bhateja, A. Taquee, and D. Sharma, “Pre-processing and classification of cough sounds in noisy environment using svm,” in _2019 4th International Conference on Information Systems and Computer Networks (ISCON)_ , 11 2019, pp. 822–826.
  * [18] S. Vhaduri, T. van Kessel, B. Ko, D. Wood, S. Wang, and T. Brunschwiler, “Nocturnal cough and snore detection in noisy environments using smartphone-microphones,” in _2019 IEEE International Conference on Healthcare Informatics (ICHI)_ , 06 2019, pp. 1–7.
  * [19] A. Winursito, R. Hidayat, and A. Bejo, “Improvement of mfcc feature extraction accuracy using pca in indonesian speech recognition,” in _2018 International Conference on Information and Communications Technology (ICOIACT)_ , 2018.
  * [20] H. D. Li, Q. S. Xu, and Y. Z. Liang, “Random frog: An efficient reversible jump markov chain monte carlo-like approach for variable selection with applications to gene selection and disease classification,” _Analytica Chimica Acta_ , vol. 740, no. none, pp. 20–26, 2012.
  * [21] Z. Wang, J. Chen, Y. Fan, Y. Cheng, X. wu, J. Zhang, B. Wang, X. Wang, T. Yong, L. Weiguo, J. Liu, J. Du, W. Yang, and F. Yang, “Evaluating photosynthetic pigment contents of maize using uve-pls based on continuous wavelet transform,” _Computers and Electronics in Agriculture_ , vol. 169, p. 105160, 02 2020.
  * [22] V. Centner, D. L. Massart, O. D. Noord, S. D. Jong, B. M. Vandeginste, and C. Sterna, “Elimination of uninformative variables for multivariate calibration,” _Analytical Chemistry_ , vol. 68, no. 21, pp. 3851–3858, 1996\.
  * [23] B. Galindo-Prieto, L. Eriksson, and J. Trygg, “Variable influence on projection (vip) for orthogonal projections to latent structures (opls),” _Journal of Chemometrics_ , vol. 28, 08 2014.
  * [24] K. Piczak, “Esc: Dataset for environmental sound classification,” in _Proceedings of the 23rd ACM International Conference on Multimedia_ , 10 2015, pp. 1015–1018.