# Training Adversarial yet Safe Agent to Characterize Safety Performance of
Highly Automated Vehicles

Minghao Zhu12, Anmol Sidhu1 and Keith A. Redmill2 1Minghao Zhu and Anmol Sidhu
are with the Advanced Mobility, Transportation Research Center Inc., East
Liberty, OH 43319, USA 2Minghao Zhu and Keith A. Redmill are with the
Department of Electrical and Computer Engineering, The Ohio State University,
Columbus, OH 43210, USA<EMAIL_ADDRESS>
###### Abstract

This paper focuses on safety performance testing and characterization of
black-box highly automated vehicles (HAV). Existing testing approaches
typically obtain the testing outcomes by deploying the HAV into a specific
testing environment. Such a testing environment can involve various passively
given testing strategies presented by other traffic participants such as (i)
the naturalistic driving policy learned from human drivers, (ii) extracted
concrete scenarios from real-world driving data, and (iii) model-based or
data-driven adversarial testing methodologies focusing on forcing safety-
critical events. The safety performance of HAV is further characterized by
analyzing the obtained testing outcomes with a particular selected measure,
such as the observed collision risk. The aforementioned testing practices
suffer from the scarcity of safety-critical events, have limited operational
design domain (ODD) coverage, or are biased toward long-tail unsafe cases.
This paper presents a novel and informative testing strategy that differs from
these existing practices. The proposal is inspired by the intuition that a
relatively safer HAV driving policy would allow the traffic vehicles to
exhibit a higher level of aggressiveness to achieve a certain fixed level of
an overall safe outcome. One can specifically characterize such a HAV and
traffic interactive strategy and use it as a safety performance indicator for
the HAV. Under the proposed testing scheme, the HAV is evaluated under its
full ODD with a reward function that represents a trade-off between safety and
adversity in generating safety-critical events. The proposed methodology is
demonstrated in simulation with various HAV designs under different
operational design domains.

##  I INTRODUCTION

Highly automated vehicles (HAV) promise to significantly improve road safety
and save lives. However, as the technology is evolving testing the safety
performance and overall effectiveness is not straight-forward. There is a rich
body of literature with many approaches to safety testing and various
standards being applied throughout the industry and regulatory agencies but
there aren’t universally accepted methods. Vehicles under test (VUT) are
usually black-boxes to testers. Putting VUTs into real traffic and observing
its performance may be a logical option but it is overly burdensome and
unpractical, especially when considering continuous modifications in each
version of the complex systems that constitute VUT. According to [1], 8.8
billion miles are needed to show its safety performance outperforms human
drivers. The huge amount of time and resources required make such real-world
testing approaches infeasible.

Scenario-based testing has become commonplace to improve testing efficiency.
As mentioned in [2], a test matrix is first determined based on real-world
data like crash data and expert knowledge. With the test matrix, some may
create a set of concrete scenarios with prescribed movements as in [3], but
this may make technology development biased to the predetermined concrete
scenarios. Others may statistically generate scenarios based on the
distribution in natural driving data (NDD) like [4]. For this case, with the
fast advancement of HAVs, the natural driving environment (NDE) changed
significantly from consisting of only human drivers to a mix of human drivers
and HAVs from various manufacturers. Handling the distribution change because
of the NDE change can be a challenge. Both scenario generation methods suffer
from their limited coverage of a VUT’s operational design domain (ODD).

Scenario generation from a test matrix parameter space covering the entire ODD
of VUT is discussed in [5]. With the increasing automation levels of HAVs, the
parameter space of a test matrix grows exponentially. To address the ”curse of
dimensionality,” deep reinforcement learning is used as mentioned in [6] to
generate testing scenarios. Moreover, testing a VUT under safety-critical
events is essential. Due to the long tail and rare nature of safety-critical
events in NDD, adversarial scenario generation is advocated in [7] [8] and [9]
to accelerate safety testing. Also, HAVs rely on their interactions with an
environment for routing planning and decision-making. It is important to
consider interactions in scenario generation as mentioned in [10].

Once the scenarios are generated, one may test the VUT on the generated
scenarios. Surrogate safety measures, including observed collision rate, time-
to-collision (TTC), and others mentioned in [11] are then used to evaluate the
testing results. The process of scenario generation and test result evaluation
is commonly referred to as scenario-based testing.

Figure 1: Typical scenarios that are less safety-related happen much more
frequently in the real world compared with safety-critical scenarios. Safety
performance can be better evaluated with safety-critical scenarios. We focus
on a subset of safety-critical scenarios, called adversarial yet safe scenario
(AYSS), to evaluate the safety performance of HAVs.

In this paper, we proposed a novel and informative scenario-based testing
method for HAV safety performance characterization. The method, instead of
testing all HAVs with a fixed set of scenarios, seeks to use principle other
vehicle (POV) policies learned from interactions with different HAVs to
characterize the safety performance of the HAVs. The POV policies are
represented by neural networks. Scenarios are generated with their initial
states sampled from a VUT’s full ODD. To learn a POV policy, one or more POVs
sharing the same POV policy are initialized around one or more VUTs sharing
the same VUT policy to interact with the VUTs. The interactions collected are
then used to optimize the POV policy based on a safety-related objective
function. With the iterative executions of the interaction and optimization, a
POV policy is selected as the safety performance characterization of the VUT
policy based on the cost of the objective function. Different POV policies
will be learned from the interactions with different VUT policies. To ensure
fairness of the testing, all POV policies are optimized based on identical
objective functions. Finally, with the intuition that a relatively safer VUT
policy would allow the POV to exhibit a higher level of aggressiveness to
achieve a certain fixed level of an overall safe outcome, the learned POV
policies are used to generate adversarial yet safe scenarios (AYSS) as shown
in Fig. 1 and compare safety performance among corresponding VUT policies. We
used two cases commonly seen in car following situations: one VUT following
one POV in the same lane and one VUT handling cut-ins of one POV from an
adjacent lane to show the effectiveness of our method. For simplicity, we
assume other functionalities of VUTs, like lane centering, are perfect, and
VUTs will not initiate lane changes during the test. Although we used car
following for the study, our method is not limited to this domain and can be
extended to systems with higher levels of automation and with more than one
VUT and POV.

Main contributions:

  1. 1.

We propose a new scenario definition
$\\{\mathcal{E}_{\pi},\mathcal{I},\mathcal{X}_{\pi^{\prime}}\\}$ which
considers the interactions between VUTs and POVs. Observations of POVs are
used to describe scenarios.

  2. 2.

AYSSs as shown in Fig. 1 generated by POV policies learned from reinforcement
learning are used to evaluate the safety performance of VUTs.

  3. 3.

The intuition that a relatively safe VUT policy would allow the POV to exhibit
a higher level of aggressiveness to achieve a certain fixed level of an
overall safe outcome is used to compare the safety performance of VUTs.

This paper is organized as follows: we review related works in Section II. In
Section III, we define the problem statement. The method is discussed in
Section IV. Two case studies on car following functionality, including same
lane following and cut-ins handling, are studied in Section V. Finally, we
offer conclusions in Section VI.

##  II RELATED WORKS

In [10], the authors proposed a comprehensive HAV testing framework. It first
generates a scenario library considering the interactions between VUTs and
POVs using reinforcement learning. Then, scenarios in the library are
adaptively selected considering the properties of a VUT for execution. Instead
of selecting scenarios from a fixed scenario library, we generate AYSSs
specific to VUTs.

As mentioned in [12], two VUT policies are compared by training POVs to
collide with VUTs. They use the first occurrence of collision in the training
as a safety performance indicator. The VUT is considered relatively safer if
its corresponding POV policy takes longer to learn how to cause a collision.
However, the first occurrence of a collision may be affected by the
optimization methoed. For example, when using stochastic gradient descent, if
the differences between two VUTs are not significant, the safety performance
of VUT may not be strongly correlated to the first occurrence of collision
observed among multiple seeds. What’s more, the scenario complexity and risk
may be different when collision first occurs for different VUTs. Thus, the
effort of learning to generate such scenarios may also be different. Thus,
simply comparing the number of episodes needed to collide may not reflect the
safety performance relation of VUTs for all cases. We propose to train POV
policies on different VUTs with certain steps and use one criterion to pick a
POV policy from all candidate POV policies obtained in training for a VUT.
Then, the POV policies are evaluated on their observation space to analyze the
safety performance of the corresponding VUT.

Authors of [13] argue that many existing safety performance testing methods
consider a VUT policy as a white box, which is not true for many situations
like third-party testing. They propose that to test a black box VUT policy,
one can train a surrogate model with similar behaviors to the VUT. Then, Monte
Carlo sampling can be used on selected key parameter spaces using the
surrogate model to understand the safety performance of the VUT. As the
complexity of VUT policy increases with the increasing automation level,
finding an appropriate surrogate model for VUT behavior learning may be
challenging. We use the same strategy to evaluate the learned model. We
utilize Monte Carlo sampling on the observation space of learned POV policy
instead of a surrogate model imitating the VUT.

##  III PROBLEM STATEMENT

To characterize the safety performance of a VUT policy, we define an HAV
testing environment containing $m$ VUTs and $n$ POVs where
$m,n\in\mathbb{Z}_{\geq 1}$. In the testing environment, VUTs can be described
by a dynamic system, $f(\cdot)$, and share a driving policy, $\pi(\cdot)$.
Consider the dynamic system

$\mathbf{s}(t+1)=f(\mathbf{s}(t),\mathbf{u}(t);\mathbf{w}(t))$ (1)

where VUT state $\mathbf{s}\in\mathcal{S}\subseteq\mathbb{R}^{s\times m}$,
action $\mathbf{u}\in\mathcal{U}\subseteq\mathbb{R}^{u\times m}$, and
disturbance $\mathbf{w}\in\mathcal{W}\subseteq\mathbb{R}^{w}$, and the policy

$\mathbf{u}(t)=\pi(\mathbf{x}(t))$ (2)

where VUT observation $\mathbf{x}\in\mathcal{X}\subseteq\mathbb{R}^{x\times
m}$. Similarly, POVs can be described by a dynamic system,
$f^{\prime}(\cdot)$, and share a driving policy, $\pi^{\prime}(\cdot)$, where

$\mathbf{s}^{\prime}(t+1)=f^{\prime}(\mathbf{s}^{\prime}(t),\mathbf{u}^{\prime}(t);\mathbf{w}(t))$
(3) $\mathbf{u}^{\prime}(t)=\pi^{\prime}(\mathbf{x}^{\prime}(t))$ (4)

with POV state
$\mathbf{s}^{\prime}\in\mathcal{S}^{\prime}\subseteq\mathbb{R}^{s^{\prime}\times
n}$, action
$\mathbf{u}^{\prime}\in\mathcal{U}^{\prime}\subseteq\mathbb{R}^{u^{\prime}\times
n}$, and observation
$\mathbf{x}^{\prime}\in\mathcal{X}^{\prime}\subseteq\mathbb{R}^{x^{\prime}\times
n}$. Testing will be executed in a structured environment with lane lines and
speed limits defined. In this paper, we would like to investigate the VUT
safety performance characterization problem in this testing environment and
compare the different VUT policies, $\pi_{1},\pi_{2},\cdots$, with the safety
performance characterizations.

##  IV METHOD

###  IV-A POV Policy Training

The POV policy is represented by a deep neural network (DNN). Transitions of
testing environment states can be modeled as a Markov Decision Process (MDP).
Such MDP is defined by tuple
$(\mathcal{X}^{\prime},\mathcal{U}^{\prime},\mathcal{P},\mathcal{R},\gamma)$,
where $\mathcal{X}^{\prime}$ is POV’s observation, $\mathcal{U}^{\prime}$
represents POV’s action, $\mathcal{P}$ denotes state transition probability,
$\mathcal{R}$ is the reward function, and $\gamma$ is the discount rate. At
each time $t$, the POV observes state $x^{\prime}_{t}$ and executes action
$u^{\prime}_{t}=\pi^{\prime}(x^{\prime}_{t})$. The environment steps to next
state according to
$\mathcal{P}=p(x^{\prime}_{t+1}|x^{\prime}_{t},u^{\prime}_{t})$. The POV is
assigned a reward $r_{t}=\mathcal{R}(x^{\prime}_{t})$. Now, a reinforcement
learning problem is formulated to obtain an optimal POV policy $\pi^{*}$ by
maximizing the expectation of discounted return,
$\mathbb{E}[\sum_{k=0}^{\infty}\gamma^{k}r_{t+k}]$.

To obtain a POV policy that generates AYSSs, we design the reward function as

$\mathcal{R}(x^{\prime}_{t})=\alpha_{A}\mathcal{R}_{A}(x^{\prime}_{t})+\alpha_{C}\mathcal{R}_{C}(x^{\prime}_{t}),$
(5)

where $\mathcal{R}_{A}$ is the adversarial reward that uses surrogate safety
measures (SSM) like distance headway and two-dimensional TTC [14] to encourage
safety critical states, $\mathcal{R}_{C}$ is the collision reward to penalize
states related to a collision, and $\alpha_{A}$, $\alpha_{C}$ are their
corresponding weights. The reward is a representation of the overall safety
outcome.

###  IV-B Scenario Generation

###### Definition 1

(Scenario) To consider the interaction between VUTs and POVs, we define a
driving scenario as a combination of three sets:
$\mathbf{z}\in\mathcal{Z}=\\{\mathcal{E}_{\pi},\mathcal{I},\mathcal{X}_{\pi^{\prime}}\\}$.
Environment $\mathcal{E_{\pi}}$ including a VUT policy $\pi$ and testing
environment like road shape, lane line, speed limit, etc., initial condition
$\mathcal{I}$, and sequential observation
$\mathcal{X}_{\pi^{\prime}}=\\{\mathcal{P}_{\pi^{\prime}}(x^{\prime},u^{\prime})\\}\subseteq\mathcal{X}^{{}^{\prime}d}$
where $d$ is the number of steps of a scenario.

To generate scenarios, firstly, we fix a VUT policy $\pi$ and a testing
environment. Then, initial conditions are sampled from the VUT’s ODD. Lastly,
POVs are placed with VUTs to obtain sequential observations for $d$ steps.

The data used to train the POV policy are the transitions
$(x^{\prime}_{t},a^{\prime}_{t},r^{\prime}_{t},x^{\prime}_{t+1})$, including
the current observations, their associated actions, rewards, and next
observations over testing steps. Transitions are collected in scenario
generation and stored in a transition buffer. Iteratively, as shown in Fig. 2,
the policy is first updated by sample transitions in the buffer and then used
to generate a new set of scenarios and add transitions included in new
scenarios to the buffer.

Figure 2: Observations in generated scenarios change as the POV police
updates.

###  IV-C Safety Performance Evaluation using AYSS

###### Definition 2

(Safety Performance Characterization Policy (SPCP)) We defined the optimal POV
policy $\pi^{*}$ obtained from training using generated scenarios as the SPCP
of VUT policy $\pi$.

To generate AYSSs with a $\pi^{*}$, we use initial states drawn from the
observation space of $\pi^{*}$ with Monte Carlo sampling. It is unpractical to
have Monte Carlo sampling with a black-box VUT policy. Thus, here, we use
$d=1$ to generate scenarios as any states after the initial states cannot be
obtained. As we focus on AYSSs, we do not want to generate typical scenarios
or scenarios with unavoidable collisions. A scenario starting from a non-
safety-critical state may take multiple steps to reach a safety-critical state
and make it a safety-critical scenario. Since the scenario step is $1$, such
scenarios should not be considered in the evaluation. Moreover, when a
scenario causes unavoidable collisions, the obtained POV action can be random,
as the outcome is the same no matter what action it takes. Therefore, such
scenarios are not AYSSs and should not be considered.

As all SPCPs are trained based on the same reward function that encourages
adversarial yet safe scenarios, we argue that all SPCPs interact with their
corresponding VUTs to achieve an identical level of overall safety outcome.
With the intuition that a relatively safer VUT policy would allow the POV
policy to exhibit a higher level of aggressiveness to achieve a certain fixed
level of an overall safety outcome, we evaluate the aggressiveness levels
using $\\{\mathcal{X}_{\pi^{*}_{1}}\\}$, $\\{\mathcal{X}_{\pi^{*}_{2}}\\}$,
and $\\{\mathcal{X}_{\pi^{*}_{n}}\\}$ and aggressiveness indicators like brake
magnitude and relative velocity projected on relative position [15] can be
used for aggressiveness comparison.

###  IV-D Safety Performance Testing Framework

As shown in Fig. 3, to test the safety performance of a set of VUT policies
$\\{\pi_{1},\pi_{2},\cdots,\pi_{n}\\}$, firstly, select a testing environment
and an initial POV policy. For each VUT policy, a copy of the initial POV
policy interacts with its respective VUT in the testing environment to
generate a scenario
$\\{\mathcal{E}_{\pi_{i}},\mathcal{I},\mathcal{X}_{\pi_{i}^{\prime[t]}}\\}$
where $d$ is the number of steps before updating POV policy
$\pi_{i}^{\prime[t]}$. The POV policies of every update are the candidates of
SPCP. After training is finished, one SPCP is selected for each VUT policy
based on the same criteria $c$. Each SPCP is then used to generate the AYSSs.
Finally, AYSSs of all VUT policies are used to evaluate their safety
performance.

Figure 3: Safety performance testing framework.

##  V CASE STUDY

Double [16] dueling [17] DQN [18] with prioritized experience replay [19]
implemented in Tianshou [20] is used here to train the POV policy. We select
discount rate $\gamma=0.8$ and learning rate $\text{lr}=10^{-5}$. The POV
policy consists of 3 fully connected neural networks: feature extraction net,
state value net, and advantage net. Each net contains two hidden layers. Each
layer contains 256 neurons. ReLU is used as the activation function. SPCP
candidates are stored and tested in 100 randomly generated scenarios every
$10000$ steps in the testing environment. An average episode reward is
recorded for each candidate. After training is finished, the candidate with
the highest average episode reward is selected as the SPCP.

Here, we choose the Intelligent Driver Model (IDM) [21] as the VUT policy. To
have two different VUT policies, $\pi_{1}$ and $\pi_{2}$, as described in
Table I, we assign minimum spacing $s_{0}=10$ m and $s_{0}=20$ m for the two
VUT policies correspondingly with all other settings the same as in [22]. We
argue that $\pi_{2}$ is relatively safer compared with $\pi_{1}$, as $\pi_{2}$
tends to keep a larger spacing with the front vehicle.

We use Highway-Env [22] as the simulation environment to construct the testing
environment with 5 Hz policy frequency and 5 seconds episode duration. VUT
speed range is $[0,40]\text{ m/s}$. VUT acceleration range is $[-6,6]\text{
m/s}^{2}$. As implemented in [22], with the knowledge of road structure (e.g.,
lane width, road network, etc.), the POV is controlled by acceleration and
steering angle, which is calculated from target speed and current and target
lane index.

We studied two cases: one-lane car-following and two-lane cut-in. To focus on
the car-following functionality modeled by IDM, we assume the VUT has perfect
lane-centering functionality and will not seek to change lanes in any
situation. In each case study, we first describe the experiment setup. Then,
AYSSs aggressiveness comparison result is shown for VUT safety performance
comparison. Lastly, SSM on AYSSs are studied to show that SPCPs generate AYSSs
that achieve an identical level of safety outcome.

$\pi$ |  $\mathbf{s}_{0}$ [m] | safety performance | expected $\pi^{*}$ behavior
---|---|---|---
$\pi_{1}$ | 10 | worse | more conservative
$\pi_{2}$ | 20 | better | more aggressive
TABLE I: Two IDMs are used as two VUT polices, $\pi_{1}$ and $\pi_{2}$. All
the IDM parameters of $\pi_{1}$ and $\pi_{2}$ are the same, except for minimum
spacing $s_{0}$. $\pi_{1}$’s safety performance is worse as $\pi_{1}$ uses a
shorter minimum spacing when making decisions than that of $\pi_{2}$. For
SPCPs generating AYSSs to reach a certain overall safety outcome,
$\pi^{*}_{1}$’s behavior is expected to be more conservative.

###  V-A One-Lane Car-Following

The testing environment is defined as a one-lane straight highway with one VUT
with policy $\pi$ following one POV with policy $\pi^{\prime}$. The VUT and
POV are initialized at the center of the lanes with headings parallel to lane
directions. The speed limit is 30 m/s. The POV observes
$\\{\mathbf{v}^{\prime},\mathbf{v},\mathbf{h}\\}$ where $\mathbf{v}^{\prime}$
is POV longitudinal speed, $\mathbf{v}$ is VUT longitudinal speed, and
$\mathbf{h}$ is distance headway. The POV action space is defined as
$\\{u^{\prime}=0.0+0.5k\\},\forall k\in\\{0,1,\cdots,20\\}$ which sets the
POV’s target speed,
$\mathbf{v}_{\text{target}}=\mathbf{u}^{\prime}\cdot\mathbf{v}^{\prime}$. The
Reward function is shown in Fig. 4. To encourage adversarial behavior, the
maximum reward occurs when $h=0.25$ m. The reward is gradually reduced and
remains zero when $h>20$ m. Collision states are penalized with minimum
reward.

Figure 4: Reward function used in one-lane car-following case study. The
maximum reward is reached when distance headway $h=0.25$ m. No reward when
$h>20$ m.

Three SPCPs are trained for each VUT policy with three seed values. We use
multiple seeds to avoid getting a POV policy by coincidence. Then, we generate
scenarios for each SPCP by conducting Monte Carlo sampling on its observation
space. The observations in the generated scenarios are used to obtain their
corresponding actions. Accelerations are calculated based on the actions. We
remove typical scenarios by assuming distance headway is less than or equal to
$5$ m. Scenarios with TTC $<0.2$ s are identified as scenarios with
unavoidable collisions.

By comparing sets of observations and actions obtained from generated
scenarios, the result is shown in Fig. 5. POVs trained with $\pi_{1}$ always
brake less hard compared with those trained with $\pi_{2}$. This comparison
result satisfies the expectation in Table I.

We also studied the overall safety outcomes of each SPCP. For each SPCP of the
two VUT policies, we generated 200 scenarios using the same process as in the
SPCP training. The overall safety outcomes of SPCPs between the two VUT
policies are similar, as shown in Table II. This shows that by using our
method, the selected SPCPs can be used to generate AYSSs that achieve a
similar level of safety outcome between VUTs with different safety
performance.

$\pi^{*}$ | $\pi$ |  $\mathbf{c}$ [%] | $\mathbf{\bar{r}}_{epi}$ |  $\mathbf{\bar{h}}$ [m]
---|---|---|---|---
1 | $\pi_{1}$ | 0 | 19.48 | 1.65
2 | $\pi_{1}$ | 0 | 19.45 | 1.82
3 | $\pi_{1}$ | 0 | 19.43 | 1.71
4 | $\pi_{2}$ | 0 | 19.30 | 2.42
5 | $\pi_{2}$ | 0 | 19.31 | 2.62
6 | $\pi_{2}$ | 0 | 19.29 | 3.76
TABLE II: Overall safety outcome study of one-lane car-following. Crash rate
$\mathbf{c}$, mean episode reward $\mathbf{\bar{r}}_{epi}$, and mean distance
headway $\mathbf{\bar{h}}$ at last step of each episode are calculated for
each SPCP $\pi^{*}$ of the two VUT policies $\pi_{1}$ and $\pi_{2}$. Figure 5:
Green and orange lines show the mean accelerations of the AYSSs generated by
SPCPs trained using three seeds with $\pi_{1}$ and $\pi_{2}$ correspondingly
over distance headways. The colored bands indicate their $95\%$ confidence
intervals.

###  V-B Two-Lane Cut-In

The testing environment is defined as a two-lane straight highway with one VUT
with policy $\pi$ and one POV with policy $\pi^{\prime}$. The POV is
initialized on the left adjacent lane of the VUT. They are initialized on the
center of their respective lanes with headings parallel to lane directions.
The speed limit is 30 m/s. The POV observes
$\\{\mathbf{v}^{\prime},\mathbf{v},\mathbf{h},\mathbf{l}\\}$ where
$\mathbf{v}^{\prime}$ is the POV longitudinal speed, $\mathbf{v}$ is the VUT
longitudinal speed, $\mathbf{h}$ is distance headway, and $\mathbf{l}$ is a
binary value indicating whether the POV and the VUT are in the same lane. The
POV action space is defined as the union of lane change action and target
speeds, $\\{\text{lane\\_change}\\}\cup\\{u^{\prime}=0.0+k\\},\forall
k\in\\{0,1,\cdots,40\\}$. The reward function consists of three parts: same
lane reward, different lane reward, and lane change reward. Firstly, it has no
reward when the VUT and the POV are in different lanes, and the POV is not
changing lanes. The rest are similar to the reward function shown in Fig. 4.
While the POV is changing lanes to encourage adversarial behavior, it receives
the maximum reward when $h=1$ m. The reward is gradually reduced and remains
zero when $h>5$ m. Collision states are penalized with minimum reward. Lastly,
the reward design is the same except for reaching maximum reward when $h=0.25$
m.

The POV policies are trained for each VUT policy three times with three seed
values. We randomly generate $100$ test cases after every $1$ epoch to
calculate a mean episode reward. The POV policy at the end of each epoch with
the highest mean episode reward is selected as the SPCP. Then, we generate
scenarios for each SPCP by conducting Monte Carlo sampling on its observation
space. The observations in the generated scenarios are used to obtain their
corresponding actions. Accelerations are calculated based on the actions. The
VUT and POV are initialized on two adjacent lanes. As the scenario length is
$1$, a scenario is safety-critical only if the action is ”lane change.” Also,
lane changing is too risky when the POV and VUT are longitudinal overlapping
along the road. Thus, scenarios with the POV rear bumper behind the VUT front
bumper are not a part of the AYSSs.

We use $\Delta\bar{\mathbf{v}}$ proposed in [15] to describe the scenario
aggressiveness here. Consider aggressiveness indicator

$\Delta\bar{\mathbf{v}}=\frac{\Delta\mathbf{p}_{ij}}{||\Delta\mathbf{p}_{ij}||}\Delta\mathbf{v}_{ij},$
(6)

where $\Delta\mathbf{v}_{ij}$ is the relative velocity vector and
$\Delta\mathbf{p}_{ij}$ is the relative position vector.
$\Delta\bar{\mathbf{v}}$ is the projection of the relative velocity vector
onto the relative position vector as shown in Fig. 6. [15] argues the relative
velocity can be decomposed into $\Delta\bar{\mathbf{v}}$ and a vector
perpendicular to the relative position vector. The latter vector acts to make
one robot rotate around the other robot and hence does not affect the
aggressiveness. Two robots are moving towards each other if
$\Delta\mathbf{\bar{v}}$ is in the opposite direction of
$\Delta\mathbf{p}_{ij}$. Hence, a system with smaller $\Delta\bar{\mathbf{v}}$
is more aggressive. As we need to consider the POV lateral movements in this
case in addition to longitudinal movements, we use $\Delta\bar{\mathbf{v}}$
here to indicate scenario aggressiveness.

The generated scenarios between SPCPs of $\pi_{1}$ and $\pi_{2}$ are compared
using $\Delta\bar{\mathbf{v}}$ over distance headway. As shown in Fig. 7, with
the same distance headways, $\Delta\bar{\mathbf{v}}$s of SPCPs of $\pi_{1}$
are greater than those of $\pi_{2}$. The result indicates that SPCPs of
$\pi_{2}$ are more aggressive than SPCPs of $\pi_{1}$. Consequently, $\pi_{2}$
has better safety performance compared with $\pi_{1}$. This conclusion matches
the IDM model analysis shown in Table I.

Similar to the one-lane car-following case, we studied the overall safety
outcome of scenarios generated by SPCPs. In addition, we calculated the lane
change rate. The result is shown in Table III. $\bar{\mathbf{r}}_{epi}$ and
$\bar{\mathbf{h}}$ are calculated using scenarios with lane changes and
without collisions. This reflects the same conclusion drawn from one-lane car-
following case that the selected SPCPs can be used to generate AYSSs that
achieve a similar level of safety outcome between VUTs with different safety
performance.

Figure 6: Aggressiveness indicator $\Delta\bar{\mathbf{v}}$ described by the projection of relative velocity onto relative position vector.  Figure 7: Green and orange lines show $\Delta\mathbf{\bar{v}}$ of the AYSSs generated by SPCPs trained using three seeds with $\pi_{1}$ and $\pi_{2}$ correspondingly over distance headways. The colored bands indicate their $95\%$ confidence intervals. $\pi^{*}$ | $\pi$ |  $\mathbf{c}$ [%] | lc [%] | $\mathbf{\bar{r}}_{epi}$ |  $\mathbf{\bar{h}}$ [m]
---|---|---|---|---|---
1 | $\pi_{1}$ | 1.0 | 99 | 20.99 | 0.36
2 | $\pi_{1}$ | 2.0 | 99 | 20.74 | 0.36
3 | $\pi_{1}$ | 0.5 | 98 | 20.78 | 0.36
4 | $\pi_{2}$ | 3.5 | 100 | 20.41 | 0.41
5 | $\pi_{2}$ | 1.0 | 100 | 20.93 | 0.38
6 | $\pi_{2}$ | 1.0 | 100 | 21.14 | 0.35
TABLE III: Overall safety outcome study of two-lane cut-in. Crash rate
$\mathbf{c}$, lane change rate lc, mean episode reward
$\mathbf{\bar{r}}_{epi}$, and mean distance headway at last step of each
episode $\mathbf{\bar{h}}$ are calculated for each SPCP $\pi^{*}$ of the two
VUT policies $\pi_{1}$ and $\pi_{2}$.

##  VI CONCLUSIONS

In this paper, we proposed a black-box HAV safety performance testing
framework and demonstrated its application in simulation. The framework
follows the intuition that a relatively safe VUT policy would allow the POV to
exhibit a higher level of aggressiveness to achieve a certain fixed level of
an overall safe outcome. We first train POVs by interacting with VUTs to reach
a certain overall safety outcome. One SPCP is selected for each VUT. SPCPs of
all VUTs are selected based on the same criteria. Then, AYSSs are generated
for each SPCP. Lastly, we compare the safety performance of VUTs by evaluating
the AYSSs. We demonstrate the effectiveness of the testing framework by
studying two cases: one-lane car-following and two-lane cut-in. In each case
study, we gave examples of the testing environment, the POV training setup,
the AYSSs generation, and their aggressiveness evaluation, and studied the
SPCPs’ overall safety outcomes. Although we studied VUTs with level-1 HAV
features here, the testing framework can be extended to higher levels of
automation. The testing framework is not limited to a single VUT. More POVs
can also be accommodated in this framework. Lastly, accelerating the POV
training can reduce the test burden with less physical VUT’s involvement.

## References

  * [1] Nidhi Kalra and Susan M. Paddock.  Driving to safety: How many miles of driving would it take to demonstrate autonomous vehicle reliability?  RAND Corporation, 2016.
  * [2] Shuo Feng, Yiheng Feng, Chunhui Yu, Yi Zhang, and Henry X. Liu.  Testing scenario library generation for connected and automated vehicles, part i: Methodology.  IEEE Transactions on Intelligent Transportation Systems, 22(3):1573–1582, 2021.
  * [3] Michiel R van Ratingen.  The EURO NCAP safety rating.  In Karosseriebautage Hamburg 2017, pages 11–20. Springer, 2017.
  * [4] Thomas A Dingus, Sheila G Klauer, Vicki Lewis Neale, Andy Petersen, Suzanne E Lee, Jeremy Sudweeks, Miguel A Perez, Jonathan Hankey, David Ramsey, Santosh Gupta, et al.  The 100-car naturalistic driving study, phase ii-results of the 100-car field experiment.  Technical report, United States. Department of Transportation. National Highway Traffic Safety, 2006.
  * [5] Bowen Weng, Minghao Zhu, and Keith Redmill.  A formal safety characterization of advanced driver assist systems in the car-following regime with scenario-sampling.  IFAC-PapersOnLine, 55(24):266–272, 2022.
  * [6] Shuo Feng, Haowei Sun, Xintao Yan, Haojie Zhu, Zhengxia Zou, Shengyin Shen, and Henry X Liu.  Dense reinforcement learning for safety validation of autonomous vehicles.  Nature, 615(7953):620–627, 2023.
  * [7] Linda Capito, Bowen Weng, Umit Ozguner, and Keith Redmill.  A modeled approach for online adversarial test of operational vehicle safety.  In 2021 American Control Conference (ACC), pages 398–404. IEEE, 2021.
  * [8] Ding Zhao, Henry Lam, Huei Peng, Shan Bao, David J LeBlanc, Kazutoshi Nobukawa, and Christopher S Pan.  Accelerated evaluation of automated vehicles safety in lane-change scenarios based on importance sampling techniques.  IEEE transactions on intelligent transportation systems, 18(3):595–607, 2016.
  * [9] Shuo Feng, Xintao Yan, Haowei Sun, Yiheng Feng, and Henry X Liu.  Intelligent driving intelligence test for autonomous vehicles with naturalistic and adversarial environment.  Nature communications, 12(1):748, 2021.
  * [10] Xinpeng Wang, Songan Zhang, and Huei Peng.  Comprehensive safety evaluation of highly automated vehicles at the roundabout scenario.  IEEE Transactions on Intelligent Transportation Systems, 23(11):20873–20888, 2022.
  * [11] Chen Wang, Yuanchang Xie, Helai Huang, and Pan Liu.  A review of surrogate safety measures and their applications in connected and automated vehicles safety modeling.  Accident Analysis & Prevention, 157:106157, 2021.
  * [12] Sampo Kuutti, Saber Fallah, and Richard Bowden.  Training adversarial agents to exploit weaknesses in deep control policies.  In 2020 IEEE International Conference on Robotics and Automation (ICRA), pages 108–114. IEEE, 2020.
  * [13] Yiyun Wang, Rongjie Yu, Shuhan Qiu, Jian Sun, and Haneen Farah.  Safety performance boundary identification of highly automated vehicles: A surrogate model-based gradient descent searching approach.  IEEE Transactions on Intelligent Transportation Systems, 23(12):23809–23820, 2022.
  * [14] Hongyu Guo, Kun Xie, and Mehdi Keyvan-Ekbatani.  Modeling driver’s evasive behavior during safety–critical lane changes: Two-dimensional time-to-collision and deep reinforcement learning.  Accident Analysis & Prevention, 186:107063, 2023.
  * [15] Urs Borrmann, Li Wang, Aaron D Ames, and Magnus Egerstedt.  Control barrier certificates for safe swarm behavior.  IFAC-PapersOnLine, 48(27):68–73, 2015.
  * [16] Hado Van Hasselt, Arthur Guez, and David Silver.  Deep reinforcement learning with double q-learning.  In Proceedings of the AAAI conference on artificial intelligence, volume 30, 2016.
  * [17] Ziyu Wang, Tom Schaul, Matteo Hessel, Hado Hasselt, Marc Lanctot, and Nando Freitas.  Dueling network architectures for deep reinforcement learning.  In International conference on machine learning, pages 1995–2003. PMLR, 2016.
  * [18] Volodymyr Mnih, Koray Kavukcuoglu, David Silver, Alex Graves, Ioannis Antonoglou, Daan Wierstra, and Martin Riedmiller.  Playing atari with deep reinforcement learning.  arXiv preprint arXiv:1312.5602, 2013.
  * [19] Tom Schaul, John Quan, Ioannis Antonoglou, and David Silver.  Prioritized experience replay.  arXiv preprint arXiv:1511.05952, 2015.
  * [20] Jiayi Weng, Huayu Chen, Dong Yan, Kaichao You, Alexis Duburcq, Minghao Zhang, Yi Su, Hang Su, and Jun Zhu.  Tianshou: A highly modularized deep reinforcement learning library.  The Journal of Machine Learning Research, 23(1):12275–12280, 2022.
  * [21] Martin Treiber, Ansgar Hennecke, and Dirk Helbing.  Congested traffic states in empirical observations and microscopic simulations.  Physical review E, 62(2):1805, 2000.
  * [22] Edouard Leurent et al.  An environment for autonomous driving decision-making.  https://github.com/Farama-Foundation/HighwayEnv, 2018.


11institutetext: Imperial College London

# Selective metamorphosis for growth modelling with applications to landmarks

Andreas Bock  Alexis Arnaudon  Colin Cotter

###### Abstract

We present a framework for shape matching in computational anatomy allowing
users control of the degree to which the matching is diffeomorphic. This
control is given as a function defined over the image and parameterises the
template deformation. By modelling localised template deformation we have a
mathematical description of growth only in specified parts of an image. The
location can either be specified from prior knowledge of the growth location
or learned from data. For simplicity, we consider landmark matching and infer
the distribution of a finite dimensional parameterisation of the control via
Markov chain Monte Carlo. Preliminary numerical results are shown and future
paths of investigation are laid out. Well-posedness of this new problem is
studied together with an analysis of the associated geodesic equations.

###### Keywords:

LDDMM Computational anatomy Metamorphosis MCMC.

##  1 Introduction

In computational anatomy [11, 12] one of the most fundamental problems is to
continuously deform an image or shape into another and thereby obtain a
natural notion of distance between them as the energy required for such a
deformation. Common methods to compute image deformations are based on
diffeomorphic deformations which assume that the images are continuously
deformed into one another with the additional property that the inverse
deformation is also continuous. This is a strong requirement for images which
implies that the ’mass’ of any part of the image is conserved: we cannot
create or close ’holes’. This is also a crucial property in fluid mechanics
and in fact the theory of diffeomorphic matching carrying the moniker _Large
Deformation Diffeomorphic Metric Mapping_ (LDDMM) [24, 5] has been inspired by
fluid mechanics. Indeed, Arnold [4] made the central observation that the
geodesic equations for the diffeomorphism group induced by divergence-free
vector fields corresponded to that of incompressible flows. If a strictly
diffeomorphic matching is not possible or necessary, an extension of LDDMM
called metamorphosis [26, 15] is available which introduces a parameter
$\sigma^{2}$ parameterising the deviation from diffeomorphic matching allowing
for topological variations e.g. growth via image intensity. In particular, if
$\sigma^{2}=0$ the deformation is purely diffeomorphic as in LDDMM. See [23,
25, 19] for technical details pertaining to the construction of the
metamorphosis problem. While diffeomorphic paths always exist for landmark
problems [13] this theory allows one to match images of shapes with different
topological features, which is ill-conditioned for standard LDDMM. Indeed,
even inexact matching in LDDMM for such problems yields large energies and
spurious geodesics that do not contribute to an intuitive matching, see figure
1. As observed here, introducing $\sigma^{2}>0$ regularises the problem and
qualitative improves the matching.

In this work, we modify metamorphosis to include a spatially dependent control
parameter $x\mapsto\nu(x)$ in order to selectively allow non-diffeomorphic
(_metamorphic_) matching in parts of the image. For $\nu(\cdot)=\sigma^{2}$
our theory recovers the standard metamorphosis model. However, with a
localised control (e.g. a Gaussian centred at a point in $\mathbb{R}^{d}$), we
can selectively introduce metamorphosis in an image and model local
topological effects such as growth phenomena. The difficulty of this problem
is to infer the function $\nu(\cdot)$ without prior knowledge of the location
of the topological effects. This problem is similar to the one treated in [3],
where such functions were parameterising the randomness in LDDMM matching of
shapes. We will use a Markov chain Monte Carlo (MCMC) approach to infer
appropriate functions $\nu(\cdot)$, such that the topological effects are well
described and a large part of the matching remains diffeomorphic. In this
paper, we focus on landmark matching but aim to extend the theory of selective
metamorphosis to data structures amenable to classical metamorphosis or LDDMM
theory can handle.

Figure 1: This figure illustrates landmark matching with classical LDDMM (left
column), metamorphosis (right column) and our selective metamorphosis approach
(middle column). LDDMM fails to perform the matching and we observe unnatural
landmark trajectories whereas metamorphosis achieves a more intuitive
matching. Selective metamorphosis has the additional advantage of only
breaking the diffeomorphic property where needed in along the matching, thus
preserving more of the desired diffeomorphic property of the matching. These
simulations where done for landmarks with Gaussian kernel of variance $0.5$,
$100$ timesteps from $t=0$ to $t=1$, and a metamorphosis kernel of variance
$0.2$.

Structure This paper is organised as follows. We review the theory of
classical metamorphosis in section 2 and extend it to selective metamorphosis
in section 3. We then introduce a Bayesian framework for inferring the
metamorphic control parameter $\nu(\cdot)$ in section 4 and apply this theory
to a few landmark examples in section 5. Section contains concluding remarks.

##  2 Metamorphosis for Landmarks

In this paper we are concerned with diffeomorphometric approaches to image and
shape matching. To this end, we use time-dependent velocity fields $u_{t}$
occupying some Hilbert space $u_{t}\in V$, where $V$ is continuously embedded
in $\textsf{C}_{0}^{k}(\mathbb{R}^{d})$, $k\geq 1$ inducing a curve
$\varphi_{t}$ on a subgroup $\text{Diff}_{V}(\mathbb{R}^{d})$ of
diffeomorphisms [4, 27] via the following ordinary differential equation

$\displaystyle\dot{\varphi_{t}}=u_{t}\circ\varphi_{t}\,,\qquad\varphi_{0}=\text{id}\,.$
(1)

This is often used in a minimisation problem where the objective is to match
two images $I_{0}$ and $I_{1}$:

$\displaystyle S(u)=\int_{0}^{1}\frac{1}{2}\|u_{t}\|_{V}^{2}\text{d}t
+\frac{1}{2\lambda^{2}}F(I_{0}\circ\varphi^{-1}_{1},I_{1})\longrightarrow\text{min.
subject to \eqref{diffeo}}\,,$ (2)

where $F$ denotes a similarity measure between the deformed initial image
$I_{0}\circ\varphi_{1}$ and the target image $I_{1}$ to allow inexact matching
parameterised by $\lambda^{2}$. The LDDMM approach takes $F$ as an $L^{2}$
norm of the difference between its arguments. In order to simplify the
exposition, we will consider singular solutions of this problem, which are
given by the Ansatz

$\displaystyle\frac{\delta l}{\delta
u}=\mathbf{m}(x)=\sum_{i=1}^{M}p_{t}^{i}\delta(x-q_{t}^{i})\,,$ (3)

for $M$ landmarks with position $q_{t}^{i}\in\mathbb{R}^{d}$ and momenta
$p_{t}^{i}\in\mathbb{R}^{d}$. The vector field is thus

$\displaystyle u_{t}(x)=\sum_{i=1}^{M}p_{t}^{i}K(x-q_{t}^{i})\,,$ (4)

where $K:\mathbb{R}^{d}\times\mathbb{R}^{d}\to\mathbb{R}$ is the kernel
associated to the norm $\|\cdot\|_{V}$. This parameterisation holds throughout
this paper and we set $d=2$. For metamorphosis, we introduce a discrete
template variable $\boldsymbol{\eta}_{t}$ such that the deformation of a set
of landmarks is written as the composition of the template position and
deformation as

$\displaystyle\mathbf{q}_{t}=\varphi_{t}\boldsymbol{\eta}_{t}\,.$ (5)

Then, we can define the template velocity as

$\displaystyle\mathbf{z}=\varphi_{t}\dot{\boldsymbol{\eta}}$ (6)

and extend the action functional (2) to

$\displaystyle\begin{split}S_{m}(\mathbf{q}_{t},\mathbf{p}_{t},\mathbf{z}_{t})=&\int_{0}^{1}\frac{1}{2}\left(\|u_{t}\|_{V}^{2}+\frac{1}{\sigma^{2}}\sum_{i=1}^{M}|z_{t}^{i}|^{2}\right)\text{d}t\,,\end{split}$
(7)

where now the reconstruction relation is

$\displaystyle\dot{\mathbf{q}_{t}}=u_{t}(\mathbf{q}_{t})+\mathbf{z}_{t}\,,$
(8)

obtained from (6) and (5) together with $u=\dot{\varphi}_{t}\varphi^{-1}$, see
[15] for more details.

By taking variations carefully, see again [15], we directly obtain a
relationship between the momentum variable $\mathbf{p}$ and the template
variable $\mathbf{z}$ as

$\displaystyle\mathbf{m}(x)=\frac{1}{\sigma^{2}}\sum_{i=1}^{M}z_{t}^{i}\delta(x-q_{i})\qquad\Rightarrow\qquad\mathbf{z}=\sigma^{2}\mathbf{p}_{i}\,,$
(9)

and the equation of motions are

$\displaystyle\begin{split}\dot{\mathbf{p}_{t}}&=-\nabla
u_{t}(\mathbf{q}_{t})^{T}\mathbf{p}_{t}\\\
\dot{\mathbf{q}_{t}}&=u_{t}(\mathbf{q}_{t})+\sigma^{2}\mathbf{p}_{t}\,,\end{split}$
(10)

where $u_{t}$ is defined in (4).

##  3 Selective Metamorphosis for Landmarks

We can now extend the metamorphosis setting to be able to locally control the
amount of non-diffeomorphic evolution. For this, we introduce a function
$\nu:\mathbb{R}^{2}\to\mathbb{R}$ replacing the parameter $\sigma^{2}$ such
that $\nu(x)=\sigma^{2}$ corresponds to the classic landmark metamorphosis.
The action for selective metamorphosis thus becomes

$\displaystyle\begin{split}S_{sm}^{\nu}(\mathbf{q}_{t},u_{t},\mathbf{z}_{t})=&\int_{0}^{1}\frac{1}{2}\left(\|u_{t}\|_{V}^{2}+\sum_{i=1}^{M}\frac{1}{\nu(q_{t}^{i})}|z_{t}^{i}|^{2}\right)\text{d}t\,,\end{split}$
(11)

which we minimise subject to the reconstruction equation (8) and the boundary
conditions $\mathbf{q}_{0}$ and $\mathbf{q}_{1}$ at time $t=0,\,1$. In the
case of landmarks we have as before that

$\displaystyle\mathbf{m}(x)=\sum_{i=1}^{M}\frac{1}{\nu(q_{t}^{i})}z_{t}^{i}\delta(x-q_{i})\qquad\Rightarrow\qquad
z_{t}^{i}=\nu(q_{t}^{i})p_{t}^{i}\quad\forall i\,,$ (12)

so we can eliminate the template variable $\mathbf{z}_{t}$ and write

$\displaystyle\begin{split}S_{sm}^{\nu}(\mathbf{q}_{t},u_{t},\mathbf{p}_{t})=&\int_{0}^{1}\frac{1}{2}\left(\|u_{t}\|_{V}^{2}+\sum_{i=1}^{M}\nu(q_{t}^{i})|p_{t}^{i}|^{2}\right)\text{d}t\,.\end{split}$
(13)

The problem defined by (13) yields the following equations for selective
metamorphosis for landmarks:

$\displaystyle\begin{split}\dot{\mathbf{p}}_{t}&=-\nabla
u_{t}(\mathbf{q}_{t})^{T}\mathbf{p}_{t}-\frac{1}{2}\nabla\nu(\mathbf{q}_{t})|\mathbf{p}_{t}|^{2}\\\
\dot{\mathbf{q}}_{t}&=u_{t}(\mathbf{q}_{t})+\nu(\mathbf{q}_{t})\mathbf{p}_{t}\,,\end{split}$
(14)

with $\mathbf{q}_{0},\,\mathbf{q}_{1}\text{ fixed}$. Again, the velocity is
fully described by $\mathbf{p}$ and $\mathbf{q}$ via (4). The landmark
dynamics follow standard LDDMM trajectories as $\nu(x)$ vanishes in parts of
the domain. This can also be seen in the relation (12), where
$\nu(x)=0\Rightarrow\mathbf{z}_{t}=0$ implies that the template variable
remains fixed. Notice that these equations are Hamilton’s equations for the
Hamiltonian $\mathbf{p}_{t}$ and $\mathbf{q}_{t}$

$\displaystyle
h(\mathbf{q},\mathbf{p})=h_{l}(\mathbf{q}_{t},\mathbf{p}_{t})+\frac{1}{2}\sum_{i}\nu(q_{i})|p_{i}|^{2}\,,$
(15)

where we have used (4) for the standard landmark Hamiltonian

$\displaystyle
h_{l}(\mathbf{q},\mathbf{p})=\frac{1}{2}\sum_{i,j=1}^{M}K(q_{i}-q_{j})p_{i}\cdot
p_{j}\,.$ (16)

A practical procedure for solving (14) with the landmark Hamiltonian above is
called _shooting_ , where we replace the end-point condition $\mathbf{q}_{1}$
with a guess for $\mathbf{p}_{0}$, and iteratively update $\mathbf{p}_{0}$
using automatically computed adjoint (or backward) equations until
$\mathbf{q}_{1}$ compares to $\mathbf{q}(1)$ below a certain tolerance. We
will perform this procedure directly with an automatic differentiation package
Theano [22], see [18, 17] for more details on the implementation. This section
concludes with some theoretical results.

###### Theorem 3.1

Let $\nu$ be bounded from below away from zero by
$\nu_{\text{inf}}\in\mathbb{R}$ and from above by $0<\sigma^{2}\in\mathbb{R}$.
Then there exists a minimiser of (13) admissible to (8).

###### Proof

The functional in (13) is not convex so we work with a reformulation to ensure
the required lower semi-continuity. Define a variable
$w^{i}_{t}=\sqrt{\nu(q_{t}^{i})}p^{i}_{t}$ in the problem:

$\displaystyle\inf_{\begin{subarray}{c}u\in L^{2}([0,1],\,V)\\\ \mathbf{q}\in
H^{1}([0,1],\,\mathbb{R}^{d\times M})\\\ \mathbf{w}\in
L^{2}([0,1],\,\mathbb{R}^{d\times M})\end{subarray}}$
$\displaystyle\int_{0}^{1}\frac{1}{2}\left(\|u_{t}\|^{2}_{V}+\sum_{i=1}^{M}|w_{t}^{i}|^{2}\right)\text{d}t$
$\displaystyle\dot{\mathbf{q}_{t}^{i}}=u_{t}(\mathbf{q}_{t})+\sqrt{\nu(\mathbf{q}_{t})}\mathbf{w}_{t}$
$\displaystyle\mathbf{q}_{0},\,\mathbf{q}_{1}\text{ fixed}$

First, note that owing to the constraint effectively being a boundary value
problem, we cannot always find a $\mathbf{q}$ for arbitrary pairs of
$(u,\,\mathbf{w})$. We define a bounded operator
$(\mathbf{q},\,u_{t})\mapsto\frac{\dot{\mathbf{q}_{t}}-u_{t}(\mathbf{q}_{t})}{\sqrt{\nu(\mathbf{q}_{t})}}\triangleq\mathbf{w}$:

$\displaystyle\Big{(}\sum_{i=1}^{M}|w_{t}^{i}|^{2}\Big{)}^{\frac{1}{2}}$
$\displaystyle=\|\mathbf{w}\|_{2}=\|\frac{\dot{\mathbf{q}}_{t}-u_{t}(\mathbf{q}_{t})}{\sqrt{\nu(\mathbf{q}_{t})}}\|_{2}\lesssim\nu_{\text{inf}}^{-1}\Big{(}\|\dot{\mathbf{q}}_{t}\|_{2}+\|u_{t}(\mathbf{q}_{t})\|_{V}\Big{)}\,.$

From this we generate a minimising sequence
$(\mathbf{q}^{n},u^{n},\mathbf{w}^{n})_{n\geq 0}$ admissible to (3). The rest
of the proof is standard, see e.g. [27]. We show the constraint equation is
continuous with respect to the weak topology on $X\triangleq
H^{1}([0,1],\,\mathbb{R}^{d\times M})\times L^{2}([0,1],\,V)\times
L^{2}([0,1],\,\mathbb{R}^{d\times M})$ i.e.
$e(\mathbf{q}_{t}^{n},\,\mathbf{w}_{t}^{n},\,u_{t}^{n})\rightharpoonup
e(\mathbf{q}_{t},\,\mathbf{w}_{t},\,u_{t})$ where
$e(q,\,w,\,u)\triangleq\dot{q}-u(q)-\sqrt{\nu(q)}w$. Then,

$\displaystyle\langle\sqrt{\nu(\mathbf{q}_{t})}\mathbf{w}_{t}-\sqrt{\nu(\mathbf{q}_{t}^{n})}\mathbf{w}_{t}^{n},\,\phi\rangle\lesssim\nu_{\text{inf}}\langle\mathbf{w}_{t}-\mathbf{w}_{t}^{n},\,\phi\rangle\rightarrow
0\,,\quad\forall\phi\in L^{2}([0,1],\,\mathbb{R}^{d\times M})\,.$

Further, for $\phi\in L^{2}([0,1],\,V)$,

$\displaystyle\langle
u_{t}(\mathbf{q}_{t})-u_{t}^{n}(\mathbf{q}_{t}^{n}),\,\phi\rangle$
$\displaystyle=\langle
u_{t}(\mathbf{q}_{t})-u_{t}^{n}(\mathbf{q}_{t}),\,\phi\rangle+\langle
u_{t}^{n}(\mathbf{q}_{t})-u^{n}(\mathbf{q}_{t}^{n}),\,\phi\rangle\,.$

The first term vanishes trivially, while for the second we see

$\displaystyle\langle
u_{t}^{n}(\mathbf{q}_{t})-u_{t}^{n}(\mathbf{q}_{t}^{n}),\,\phi\rangle\leq\text{Lip}(u_{t}^{n})\langle\mathbf{q}_{t}-\mathbf{q}_{t}^{n},\,\phi\rangle\rightarrow
0$

Since linear operators are naturally compatible with the weak topology the
required continuity follows. Passing to subsequences where necessary we can by
classic results extract bounded subsequences converging to weak limits where
necessary to obtain a minimiser. Convexity of $S$ implies weak lower semi-
continuity concluding the proof. $\square$

###### Theorem 3.2

Assume $\nu\in W^{2,\infty}(\mathbb{R}^{d})$ and $V$ is embedded in
$\textsf{C}_{0}^{k}(\mathbb{R}^{d})$, $k\geq 1$ (continuous functions with
continuous derivatives to order $k$ vanishing at infinity). Then, given
$\mathbf{p}_{0},\,\mathbf{q}_{0},\in\mathbb{R}^{d\times M}$, (14) with (4) are
integrable for all time.

###### Proof

Establishing appropriate Lipschitz conditions implies integrability of the
system akin to [6, Theorem 5]. We note that the kernel in (4) is Lipschitz in
$(p_{t},q_{t})$ by assumption, so the composition $(p,\,q)\mapsto u\circ q$ is
also Lipschitz. $u(q)\mapsto\nabla u(q)^{T}$ consider $v,\,w\in V$ and
$x,\,y\in\mathbb{R}^{d}$:

$\displaystyle\|\nabla v(x)-\nabla
w(y)\|_{2}\lesssim\|v\|_{V}\|x-y\|_{2}+\|v-w\|_{V}\|y\|_{2}$ (17)

so the mapping is Lipschitz in both the position and velocity. Given the
conditions on $\nu$ the mappings

$\displaystyle\begin{split}&(q,\,p)\mapsto\nu(q)p\\\
&(q,\,p)\mapsto\nabla\nu(q)|p|^{2}\end{split}$ (18)

are locally Lipschitz. Consequently we verify that for any
$(\mathbf{p}_{0},\,\mathbf{q}_{0})\in B(0,r)\subset\mathbb{R}^{d\times
M}\times\mathbb{R}^{d\times M}$, the system (14) is locally Lipschitz with
constant $L_{r,t_{0}}$ for some $t_{0}>0$. By the conservation of the
Hamiltonian we can extend the existence of solutions to arbitary $t>t_{0}$.
$\square$

##  4 Bayesian Framework

We now place a stochastic model on $\nu$ inspired by the approach taken in
[6], see also [21, 1, 2] for similar Bayesian approaches in computational
anatomy. The goal is to develop an algorithm to infer $\nu$, passing via the
deterministic problem seen above. First, we present some preliminaries on the
Bayesian approach to inverse problems in section 4.1, essentially quoting
concepts and results from [9], or [7] for an exposition of algorithmic aspects
of function space MCMC. Section 4.2 then formally describes how we apply this
stochastic approach to inverse problems to $\nu$ by a finite-dimensional
family of parameterisations.

###  4.1 General Framework

The general framework is based on the idea that we can cast optimisation
problems in a probabilistic framework where minimisers, roughly speaking,
correspond to modes of a certain distribution over function space. In the
context of optimisation we define a _likelihood_ $\Phi:X\rightarrow Y$,
mapping some control variable in $X$ to an observable in $Y$. A _maximum a
posteriori_ (MAP) estimator $f^{*}$ satisfies $f^{*}=\arg\max_{f\in
X}\Phi(f)p(f)$ where $p$ is a density over $X$. Equipped with a norm
$\|\cdot\|_{X}$ we can then define the Gaussian density by $p(\cdot)\propto
e^{-\|\cdot\|_{X}^{2}}$. Supposing further that the likelihood is on the form
$\log\Phi(f)=-\|f-\lambda\|_{Y}^{2}$, for some desiderata $\lambda\in Y$ then,
at least formally, the MAP estimator minimises
$J=\|f^{*}\|_{X}^{2}+\|f^{*}-\lambda\|_{Y}^{2}$.

For general inverse problems on function space, several key properties
documented in [9] must be verified before the inverse problem is well-posed.
Beyond showing the existence of the MAP estimator minimising $J$ above, the
infinite-dimensional version of Bayes’ rule must also be checked i.e. the
Radon-Nikodym derivative of the prior with respect to the posterior must exist
and be absolutely continuous. Finally, we request continuity of the posterior
distribution w.r.t the initial data corresponding in a sense to Hadamard well-
posedness in a probabilistic framework. Rigorously treating this Bayesian
inverse problem is subject to further study in forthcoming works.

###  4.2 Finite-dimensional Parameterisation

We now introduce the main problem of this paper in the setting above. We
consider $\nu$ as a random variable. If the growth location is not known _a
priori_ , then this is an appropriate framework as it allows for a qualitative
evaluation of selective metamorphosis. Moreover, it can account for some
observation error by its probabilistic nature. As a simple example, we
consider the case where $\nu$ is given by a sum of Gaussians

$\nu_{h}(x)=\sum_{k=1}^{K}e^{-\sigma_{\nu}^{-2}\|h_{k}-x\|_{\mathbb{R}^{d}}^{2}}\,.$
(19)

Here the finite family $h_{k}$ of centroids in $\mathbb{R}^{d}$ together with
the uniform length-scale $\sigma_{\nu}$ fully determine $\nu_{h}$, thus
greatly reducing the complexity of sampling. We defer sampling from function
space to future work. Defining a density $p_{sm}\propto e^{-S_{sm}^{\nu}}$
over the space of triples $(\nu,\,\mathbf{q}_{\nu},\,\mathbf{p}_{\nu})$ leads
to the preconditioned Crank-Nicholson algorithm 1, see e.g. [14].

procedure mcmcSM($N$, $K$, $\mathbf{q}_{0}$, $\mathbf{q}_{1}$,
$\beta\in(0,1]$)

$j\leftarrow 1$

$\nu^{j}\leftarrow\text{initial guess in }\mathbb{R}^{d\times K}$

Solve (14) with $\nu^{j}$ and $\mathbf{q}_{0},\,\mathbf{q}_{1}$ to obtain
$\omega^{j}=(\mathbf{q}^{j},\,\mathbf{p}^{j},\,u^{j})$

while $j<N$ do

Sample a random point $\xi\in\mathcal{N}(0,\text{Id}_{\mathbb{R}^{d}})^{K}$

$\nu\leftarrow\beta\xi+\sqrt{1-\beta^{2}}\nu^{j}$

Solve (14) with $\nu$ and $\mathbf{q}_{0},\,\mathbf{q}_{1}$ to obtain
$\omega=(\mathbf{q},\,\mathbf{p},\,u)$

if
randomUnit()$\,<\min(1,\,e^{-S_{sm}^{\nu^{j}}(\omega^{j})+S_{sm}^{\nu}(\omega)})$
then

$\nu^{j+1}\leftarrow\nu$

$\omega^{j+1}\leftarrow\omega$

else

$\nu^{j+1}\leftarrow\nu^{j}$

$\omega^{j+1}\leftarrow\omega^{j}$

$j\leftarrow j+1$ return $\\{\nu^{j},\,\omega^{j}\\}_{j=1}^{N}$

Algorithm 1 MCMC for selective metamorphosis

Here, $N$ denotes the desired number of samples and $K$ the number of terms in
(19). randomUnit() denotes a randomly generated number in $[0,\,1]$. The
coefficient $\beta$ scales between the previous sample and the new step $\xi$.
This needs to be calibrated as a too low value may increase the acceptance
rate by taking shorter steps at the cost of slow exploration of the state
space. Conversely, a too high value of $\beta$ results in lower acceptance and
thus convergence. The next section shows the algorithm above in practice.

##  5 Numerical examples

This section displays some numerical results for our method. We apply
algorithm 1 to infer a distribution for the growth location using the landmark
boundary conditions seen in figure 1. The parameters and results for the first
configuration is shown in figure 2. These preliminary results demonstrate that
even for a small number of samples the density of accepted samples corresponds
at least heuristically to the analytical density histogram obtained by
computing the value of the metamorphosis functional in (11).

Figure 2: We display the result of the MCMC algorithm 1 applied to the
inverted landmarks example of figure 1. The top left panel shows the
analytical values for the functional (11) obtained for various positions of a
single Gaussian $\nu$. We observe a bimodal minimum near $(0,0)$, which
depends on the choice of the model parameters, and in particular on the
landmark interaction length corresponding to the Gaussian kernel $K$ and
$\sigma_{\nu}$. The top middle panel displays a heat map for the sampled
positions of the centroid from the MCMC method, where the bimodality is not
clearly visible. The top right panel is a histogram of the sampled values of
the functional which rapidly decays, indicating a good sampling of the minimum
value of the functional. The bottom left panel shows the autocorrelation
function of the Markov chain, which decays rapidly to reach an un-correlated
state after $50$ iterations. The bottom right panel is one of the MAP
estimators where the centroid is near on the edge of one of the wells of the
top left panel. The simulations parameters are set to $\sigma_{\nu}=0.2$, and
$0.7$ for the velocity kernel, $K=1$ and $\beta=0.2$ across $5000$ samples.

We arrive at the same conclusion for the second example, for which the results
are shown in figure (3). Moreover, we note that the geodesic equations for $p$
and $q$ are time-reversible meaning that the configuration in figure 3
corresponds to both particle collapse as well as hole creation.

Figure 3:  Here we display the results for the second example (landmark
collapse) of figure 1. Again, the top left panel shows the analytical values
for a single $\nu$ field (11), which has also a bimodal structure, but in the
other direction. For the MCMC we choose $K=2$ Gaussian $\nu$ fields, and the
top middle and right displays two heat maps for the sampled positions of these
centroids. The bottom left panel is a histogram of the sampled values of the
functional, which has a peak at slightly higher values, possibly due to the
redundant choice of two $\nu$ functions. The bottom middle panel is the
autocorrelation function of the Markov chain which shows decorrelation after
$100$ steps. The bottom right panel shows the geodesics yielding one of the
lowest functional values, where the two $\nu$ fields are close to each other,
demonstrating the fact that only $1$ would have been enough for this landmark
configuration. The simulation parameters are the same as in figure 2 with the
exception of $K=2$.

It is numerically relatively simple to control the behaviour of $\nu$ by
simple scaling or by adding regularisation terms to (11) to e.g. penalise
having $\nu$’s far away from the support of the images. Such cost can easily
be added to the MCMC algorithm, depending on the prior information one can
have on the shape matching problem.

##  6 Conclusion

We have presented a preliminary approach for selectively allowing photometric
variation in a diffeomorphic image matching. We analysed the selective
metamorphosis problem, the associated geodesic equations and demonstrated a
proof of concept MCMC algorithm inferring a simple parameterisation of $\nu$.
This generalises LDDMM and metamorphosis and could provide a first-order
exploratory tool for physicians to see if the development of a biological
feature stems from a few violations of diffeomorphic evolution. This paper
paves the way towards surgically investigating growth phenomena between
topologically different images.

Future work is manifold. Firstly, we aim to extend the equations of section 3
to images e.g. using the kernel framework in [20] or developing a space-time
method. We also aim to find an explicit solution to the geodesic equations for
$\mathbf{p}$ and $\mathbf{q}$ and with the additional terms involving $\nu$ à
la [25] to eliminate the need $\nu$ to be bounded from below. Further, as
outlined in 4 there are many aspects of the probabilistic framework that need
rigorous treatment. Beyond the references therein, see also the work in [8].
Natural extensions of our probabilistic approach also include fully treating
$\nu$ as a function and interpreting the resulting inverse problem through the
appropriate measure-theoretical lens. Adding a time-dependency to $\nu$ can
also be explored. Determining a truncated Fourier series of $\nu$ could lead
to efficient numerical methods. More generally, we hope to reconcile our
attempts to model growth here with the mathematically elegant approach
described in [16] and with the more general mathematics of growth [10].

Finally, it is our hope that we can extend the probabilistic approach
developed here to encompass classic metamorphosis as well; that is to say, to
develop the necessary theory in order to place a stochastic model on the state
space consisting of velocities and source functions and sample from function
space. This provides a derivative-free method of solving classic metamorphosis
(or other problems in shape analysis) at the expense of interpreting the
results probabilistically. In this work, we only used a simple MCMC algorithm,
but a Metropolis-adjusted Langevin algorithm or Hamiltonian Monte-Carlo
algorithm may be more appropriate to solve this problem.

### Acknowledgements

AA acknowledges EPSRC funding through award EP/N014529/1 via the EPSRC Centre
for Mathematics of Precision Healthcare.

## References

  * [1] S. Allassonnière, Y. Amit, and A. Trouvé.  Towards a coherent statistical framework for dense deformable template estimation.  Journal of the Royal Statistical Society: Series B (Statistical Methodology), 69(1):3–29, 2007.
  * [2] S. Allassonnière, E. Kuhn, and A. Trouvé.  Map estimation of statistical deformable templates via nonlinear mixed effects models: Deterministic and stochastic approaches.  In 2nd MICCAI Workshop on Mathematical Foundations of Computational Anatomy, pages 80–91, 2008.
  * [3] A. Arnaudon, D. D. Holm, and S. Sommer.  A Geometric Framework for Stochastic Shape Analysis.  Foundations of Computational Mathematics, 2018.
  * [4] V. I. Arnold.  Sur la géométrie différentielle des groupes de lie de dimension infinie et ses applicationsa l’hydrodynamique des fluides parfaits.  Ann. Inst. Fourier, 16(1):319–361, 1966.
  * [5] M. F. Beg, M. I. Miller, A. Trouvé, and L. Younes.  Computing large deformation metric mappings via geodesic flows of diffeomorphisms.  International Journal of Computer Vision, 61(2):139–157, 2005\.
  * [6] C. J. Cotter, S. L. Cotter, and F.-X. Vialard.  Bayesian data assimilation in shape registration.  Inverse Problems, 29(4):045011, 2013.
  * [7] S. L. Cotter, G. O. Roberts, A. M. Stuart, and D. White.  MCMC methods for functions: modifying old algorithms to make them faster.  Statistical Science, pages 424–446, 2013.
  * [8] M. Dashti, K. J. Law, A. M. Stuart, and J. Voss.  MAP estimators and their consistency in bayesian nonparametric inverse problems.  Inverse Problems, 29(9):095017, 2013.
  * [9] M. Dashti and A. M. Stuart.  The Bayesian approach to inverse problems.  Handbook of Uncertainty Quantification, pages 311–428, 2017.
  * [10] A. Goriely.  The mathematics and mechanics of biological growth, volume 45.  Springer, 2017.
  * [11] U. Grenander and M. I. Miller.  Representations of knowledge in complex systems.  Journal of the Royal Statistical Society. Series B (Methodological), pages 549–603, 1994.
  * [12] U. Grenander and M. I. Miller.  Computational anatomy: An emerging discipline.  Quarterly of applied mathematics, 56(4):617–694, 1998.
  * [13] H. Guo, A. Rangarajan, and S. Joshi.  Diffeomorphic point matching.  In Handbook of Mathematical Models in Computer Vision, pages 205–219. Springer, 2006.
  * [14] M. Hairer, A. M. Stuart, S. J. Vollmer, et al.  Spectral gaps for a metropolis–hastings algorithm in infinite dimensions.  The Annals of Applied Probability, 24(6):2455–2490, 2014.
  * [15] D. Holm, A. Trouvé, and L. Younes.  The Euler-Poincaré theory of metamorphosis.  Quarterly of Applied Mathematics, 67(4):661–685, 2009.
  * [16] I. Kaltenmark.  Geometrical Growth Models for Computational Anatomy.  PhD thesis, Université Paris-Saclay, 2016.
  * [17] L. Kühnel, A. Arnaudon, and S. Sommer.  Differential geometry and stochastic dynamics with deep learning numerics.  arXiv preprint arXiv:1712.08364, 2017.
  * [18] L. Kühnel and S. Sommer.  Computational anatomy in Theano.  In Graphs in Biomedical Image Analysis, Computational Anatomy and Imaging Genetics, pages 164–176. Springer, 2017.
  * [19] M. I. Miller and L. Younes.  Group actions, homeomorphisms, and matching: A general framework.  International Journal of Computer Vision, 41(1-2):61–84, 2001.
  * [20] C. L. Richardson and L. Younes.  Metamorphosis of images in reproducing kernel Hilbert spaces.  Advances in Computational Mathematics, 42(3):573–603, 2016.
  * [21] J.-B. Schiratti, S. Allassonnière, O. Colliot, and S. Durrleman.  A Bayesian mixed-effects model to learn trajectories of changes from repeated manifold-valued observations.  The Journal of Machine Learning Research, 18(1):4840–4872, 2017\.
  * [22] T. T. D. Team, R. Al-Rfou, G. Alain, A. Almahairi, C. Angermueller, D. Bahdanau, N. Ballas, F. Bastien, J. Bayer, A. Belikov, et al.  Theano: A Python framework for fast computation of mathematical expressions.  arXiv preprint arXiv:1605.02688, 2016.
  * [23] A. Trouvé.  An infinite dimensional group approach for physics based models in pattern recognition.  Preprint, 1995.
  * [24] A. Trouvé.  Diffeomorphisms groups and pattern matching in image analysis.  International Journal of Computer Vision, 28(3):213–221, 1998.
  * [25] A. Trouvé and L. Younes.  Local geometry of deformable templates.  SIAM Journal on Mathematical Analysis, 37(1):17–59, 2005.
  * [26] A. Trouvé and L. Younes.  Metamorphoses through Lie group action.  Foundations of Computational Mathematics, 5(2):173–198, 2005.
  * [27] L. Younes.  Shapes and diffeomorphisms, volume 171.  Springer Science & Business Media, 2010.


Copyright for this paper by its authors. Use permitted under Creative Commons
License Attribution 4.0 International (CC BY 4.0).

Forum for Information Retrieval Evaluation, December 13-17, 2021, India

<EMAIL_ADDRESS>]

<EMAIL_ADDRESS>]

<EMAIL_ADDRESS>]

# IIITDWD-ShankarB@ Dravidian-CodeMixi-HASOC2021: mBERT based model for
identification of offensive content in south Indian languages

Shankar Biradar  Indian Institute of Information Technology Dharwad,  Sunil
Saumya  Indian Institute of Information Technology Dharwad  Arun Chauhan
Graphic Era University Dehradun

(2021)

###### Abstract

In recent years, there has been a lot of focus on offensive content. The
amount of offensive content generated by social media is increasing at an
alarming rate. This created a greater need to address this issue than ever
before. To address these issues, the organizers of “Dravidian-Code Mixed
HASOC-2020” have created two challenges. Task 1 involves identifying offensive
content in Malayalam data, whereas Task 2 includes Malayalam and Tamil Code
Mixed Sentences. Our team participated in Task 2. In our suggested model, we
experiment with multilingual BERT to extract features, and three different
classifiers are used on extracted features. Our model received a weighted F1
score of 0.70 for Malayalam data and was ranked fifth; we also received a
weighted F1 score of 0.573 for Tamil Code Mixed data and were ranked eleventh.

###### keywords:

Offensive mBERT CodeMixed SVM

##  1 Introduction

The availability of smart phones and the internet has created a great deal of
interest in social media among today’s youth. These applications give a huge
platform for users to connect with the outside world and share their ideas and
opinions with others. With these benefits comes a disadvantage: under the name
of freedom to express one on social media, many people misuse the platform.
People tend to publish inflammatory content on social media. This inflammatory
information typically targets a single person, a group of people, a particular
faith, or a community [1]. People generate objectionable content and
aggressively propagate it on social media in the lack of regulatory
restraints. This type of material is produced for a variety of reasons,
including commercial and political gain [2]. If not identified, this type of
content has the ability to disrupt social harmony and cause riots in society.
Also, it has the potential to have a detrimental psychological influence on
the readers. It can have a negative impact on people’s emotions and conduct.
Therefore, identifying this type of content is critical; as a result,
researchers, policymakers, and investors (stakeholders) are attempting to
develop a dependable technique to identify offensive content on social media
[3].

Various studies on hate speech, harmful content, and abusive language
identification in social media have been conducted during the previous decade.
The majority of these studies were focused on monolingual English content and
a large amount of English language cuprous has been created [4]. But, people
in countries with a complex culture and history, such as India, frequently use
regional languages to generate inappropriate social media posts. Users
typically mix their regional languages with English while creating such
content. This type of text is known as code mixed text on social media. Hence
we require efficient method to classify offensive content in Code-Mixed Indian
languages. In this context, the “Dravidian-CodeMixed HASOC-2020” shared task
provider has organized two tasks for detecting hate speech in Dravidian
languages such as Malayalam and Tamil code-mixed data. Our team took part in
Task No. 2, and this paper presents the working notes for our suggested model.

The rest of the article is arranged in the following manner: Section 2
provides a brief summary of previous work, while Section 3 describes the
proposed model in full. Section 4 concludes by providing information on the
outcome.

##  2 Literature review

A large number of researchers and practitioners from industry and academia
have been attracted to the subject of automatic identification of hostile and
harmful speech. [5] Provides a high-level review of current state-of-the-art
in offensive language identification and related issues, such as hate speech
recognition. [6] Developed a publicly accessible dataset for identifying
offensive language in tweets by categorizing them as hate speech, offensive
but not hate speech, or neither. Various machine learning models, such as
Support Vector Machine (SVM) and logistic regression, were created utilizing
various data properties, such as n-grams, TF-IDF, readability, and so on. [7]
Built a model with deep neural networks in combination with SVM for the
detection of offensive content with the accomplishment of F1 score of 90. [8]
Provided a code mixed data set for Malayalam-English language and attained a
base line result of 75% F1 score using BERT’s transformer model.

Offensive content detection from tweets is part of some conferences as
challenging tasks. Offensive 2020, a task in five languages, was provided by
SemEval in 2020 as a task in five languages, namely English, Arabic, Danish,
Greek, and Turkish [9]. In FIRE 2019, a similar task was achieved for Indo-
European languages such as English, Hindi, and German. The data set was
created using samples obtained on Twitter and Face book in all three
languages. Various models, including LSTM with attention, Word2vec embedding
with CNN, and BERT, were used for this task. In several cases, traditional
learning models, outperformed deep learning methods for language other than
English [10].

##  3 Task and Data set description

We have taken data set from HASOC subtask, offensive language identification
of Dravidian CodeMix[11]. Challenges provided by the organizers are as
follows.

Task 1: It is a binary classification problem with message level labeling for
offensive and non-offensive information in Malayalam CodeMixed YouTube
comments.

Task 2: Given Romanized Tanglish and Manglish tweeter or YouTube comments, the
system must classify them as offensive or non-offensive.

Our team took part in Task 2 for identifying offensive information in the
Tanglish and Manglish data sets. According to organizer Tanglish data is
collected from twitter tweets and comment on hello APP. Whereas Manglish data
is taken from YouTube comments [11]. Detailed description of the data set is
provided in Table 1, both Tanglish and Manglish data contain ID, Tweet and
Label fields.

Table 1: data set description Task | Data set | Offensive | Not-offensive | Total
---|---|---|---|---
Tanglish | Train | 1980 | 2020 | 4000
Test | 475 | 465 | 940
Manglish | Train | 1953 | 2047 | 4000
Test | 512 | 488 | 1000

##  4 Methdology

Our team has proposed three submissions based on three different models, each
of which is designed using the general architecture shown in fig 1. Our model
consists of three stages, each of which is discussed in the preceding
subsections.

Figure 1: General architecture of classifier model

###  4.1 Data processing

data set provided by the organizer contains many unwanted information, few
data preprocessing steps were undertaken on both text and label fields to
convert the data suitable for model building. Digits, special characters,
hyperlinks, and tweeter user handles were omitted from the data set because
they were not helping us improve the performance of our model. Furthermore,
the social media data provided by the organizer did not follow grammatical
norms; hence, data lemmatization is performed to convert the data to its
useable base form. Example, word ate, eaten and eating are converted to its
base form eat. Converting text to lower case is also done. All of this
preprocessing was done with the help of the NLTK toolbox from the Python
library [12]. The preprocessed data is then fed into a tokenizer, which
divides the tweet into a number of tokens. The mBERT tokanizer
111https://huggingface.co/bert-base-multilingual-cased  is used for this
purpose. Padding and masking were also used to handle variable length
sentences.

###  4.2 Feature extraction

To obtain contextual embeddings from CodeMixed data, we employed the
multilingual Bidirectional Encoder Representation (mBERT) model [13]. The
architecture of the mBERT model is largely based on the original BERT
architecture [14], which has 12 transformer blocks, 12 attention heads, and
768 hidden layers. Furthermore, the vector dimension of mBERT embeddings is
768. This model was trained using the same pre-training technique as the BERT,
namely Masked Language Modeling (MLM) and Next Sentence Prediction. The only
distinction is that multilingual BERT is trained on Wikipedia data from 104
different languages in order to handle languages other than English. For our
classification purposes, we only draw embeddings from the CLS token at the
beginning because it gives whole sentence embeddings.

###  4.3 Classification

In our suggested model we experiment with three different classifiers the
description of these models is provided in following subsections

####  4.3.1 Traditional machine learning based classifier

The initial studies were carried out utilizing typical machine algorithms such
as Support Vector Machine (SVM) with a 10 fold cross validation. The
experimental findings for the proposed model show that hyper-parameters of
kernel value ’1’ and solver ’lbfgs’ yield best results. This model takes an
input vector from mBERT and produces labels that are either offensive or non-
offensive. Python’s scikit-learn library is used to implement the model [15].

####  4.3.2 Deep neural network based model

Later, we experimented with the DNN, which in our suggested strategy serves as
a second model. The DNN model consists of several dense layers designed to
significantly shape and compress the input. Each dense layer follows a drop-
out layer to prevent over fitting problem. We also have a batch normalization
layer to normalize activation values. Embeddings obtained from mBERT is given
as input this classifier.

####  4.3.3 Transformer model

We explored on transformer-based models in our last model. Transformer
architectures are trained on generic tasks such as modeling language and can
then be perfectly adjusted for classification purposes. BERT developers
provide simple classification API, I’e Bert-base-uncased is underlying model
for our classification.

##  5 Experimental Results

Table 2: Top performing models on Manglish data set Team name | Precision | Recall | F1 score | Rank
---|---|---|---|---
AIML | 0.776 | 0.762 | 0.766 | 1
MUCIC | 0.764 | 0.76 | 0.762 | 2
HSU | 0.744 | 0.73 | 0.735 | 3
IIIT Surat | 0.752 | 0.727 | 0.734 | 4
IRLab | 0.754 | 0.705 | 0.714 | 5
IIITD-ShankarB | 0.715 | 0.693 | 0.7 | 6

To evaluate presented models, the organizers have provided a weighted F1
score. Among the proposed models, our top performing model came in sixth place
for offensive content recognition in the Mangalish data set and eleventh place
in the Tanglish data set, Table 2 and Table 3 provides the list of top
performing models with weighted F1 score for Manglish and Tanglish data set
respectively [The result of our proposed model is shown in bold letters]. We
trained our proposed model on Tanglish data set of 4000 comments from the
training set and tested on 940 comments from the test set. For the Manglish
data set, 4000 train comments and 1000 test comments are employed.

Table 3: Top performing models on Tanglish data set Team name | Precision | Recall | F1 score | Rank
---|---|---|---|---
MUCIC | 0.679 | 0.685 | 0.678 | 1
AIML 2 | 0.67 | 0.67 | 0.67 | 2
SSN_IT_NLP | 0.685 | 0.688 | 0.668 | 3
ZYBank AI | 0.671 | 0.676 | 0.654 | 4
IRLab | 0.654 | 0.662 | 0.65 | 5
IIITD-ShankarB | 0.599 | 0.568 | 0.573 | 11

##  6 Conclusion and future enhancement

In our article we presented model submitted by our team IIITD-ShankarB for
offensive content identification in shared task “Dravidian-CodeMixed
HASOC-2020”. In our proposed work, we experimented with three distinct models,
including a machine learning-based model, a deep Neural Network model, and a
transformer-based language model. Our model is one of the top performing
models, ranking sixth on the Manglish data set and eleventh on the Tanglish
data set. In future work, we can improve the efficiency of the suggested model
by including domain-specific embeddings.

## References

  * Chowdhury et al. [2020] S. A. Chowdhury, H. Mubarak, A. Abdelali, S.-g. Jung, B. J. Jansen, J. Salminen,  A multi-platform arabic news comment dataset for offensive language detection,  in: Proceedings of the 12th Language Resources and Evaluation Conference, 2020, pp. 6203–6212.
  * Santos et al. [2018] C. N. d. Santos, I. Melnyk, I. Padhi,  Fighting offensive language on social media with unsupervised text style transfer,  arXiv preprint arXiv:1805.07685 (2018).
  * Kumar et al. [2020] R. Kumar, A. K. Ojha, B. Lahiri, M. Zampieri, S. Malmasi, V. Murdock, D. Kadar,  Proceedings of the second workshop on trolling, aggression and cyberbullying,  in: Proceedings of the Second Workshop on Trolling, Aggression and Cyberbullying, 2020.
  * Mubarak et al. [2017] H. Mubarak, K. Darwish, W. Magdy,  Abusive language detection on arabic social media,  in: Proceedings of the first workshop on abusive language online, 2017, pp. 52–56.
  * Fortuna and Nunes [2018] P. Fortuna, S. Nunes,  A survey on automatic detection of hate speech in text,  ACM Computing Surveys (CSUR) 51 (2018) 1–30.
  * Davidson et al. [2017] T. Davidson, D. Warmsley, M. Macy, I. Weber,  Automated hate speech detection and the problem of offensive language,  in: Proceedings of the International AAAI Conference on Web and Social Media, volume 11, 2017\.
  * Al-Khalifa et al. [2020] H. Al-Khalifa, W. Magdy, K. Darwish, T. Elsayed, H. Mubarak,  Proceedings of the 4th workshop on open-source arabic corpora and processing tools, with a shared task on offensive language detection,  in: Proceedings of the 4th Workshop on Open-Source Arabic Corpora and Processing Tools, with a Shared Task on Offensive Language Detection, 2020.
  * Chakravarthi et al. [2020] B. R. Chakravarthi, N. Jose, S. Suryawanshi, E. Sherly, J. P. McCrae,  A sentiment analysis dataset for code-mixed malayalam-english,  arXiv preprint arXiv:2006.00210 (2020).
  * Zampieri et al. [2020] M. Zampieri, P. Nakov, S. Rosenthal, P. Atanasova, G. Karadzhov, H. Mubarak, L. Derczynski, Z. Pitenis, Ç. Çöltekin,  Semeval-2020 task 12: Multilingual offensive language identification in social media (offenseval 2020),  arXiv preprint arXiv:2006.07235 (2020).
  * Mandl et al. [2019] T. Mandl, S. Modha, P. Majumder, D. Patel, M. Dave, C. Mandlia, A. Patel,  Overview of the hasoc track at fire 2019: Hate speech and offensive content identification in indo-european languages,  in: Proceedings of the 11th forum for information retrieval evaluation, 2019, pp. 14–17.
  * Chakravarthi et al. [2021] B. R. Chakravarthi, P. K. Kumaresan, R. Sakuntharaj, A. K. Madasamy, S. Thavareesan, P. B, S. Chinnaudayar Navaneethakrishnan, J. P. McCrae, T. Mandl,  Overview of the HASOC-DravidianCodeMix Shared Task on Offensive Language Detection in Tamil and Malayalam,  in: Working Notes of FIRE 2021 - Forum for Information Retrieval Evaluation, CEUR, 2021\.
  * Bird et al. [2009] S. Bird, E. Klein, E. Loper, Natural language processing with Python: analyzing text with the natural language toolkit, " O’Reilly Media, Inc.", 2009.
  * Pires et al. [2019] T. Pires, E. Schlinger, D. Garrette,  How multilingual is multilingual bert?,  arXiv preprint arXiv:1906.01502 (2019).
  * Devlin et al. [2018] J. Devlin, M.-W. Chang, K. Lee, K. Toutanova,  Bert: Pre-training of deep bidirectional transformers for language understanding,  arXiv preprint arXiv:1810.04805 (2018).
  * Pedregosa et al. [2011] F. Pedregosa, G. Varoquaux, A. Gramfort, V. Michel, B. Thirion, O. Grisel, M. Blondel, P. Prettenhofer, R. Weiss, V. Dubourg, et al.,  Scikit-learn: Machine learning in python. the journal of machine learning research 12 (2011).