# A New Hybrid Automaton Framework with Partial Differential Equation Dynamics

Tianshu Bao  Hengrong Du  Weiming Xiang  and Taylor T. Johnson  Institute for
Software Integrated Systems, Vanderbilt University, Nashville TN 37240, USA
Department of Mathematics, Vanderbilt University, Nashville TN 37240, USA
School of Computer and Cyber Sciences, Augusta University, Augusta, GA 30912,
USA

###### Abstract

This paper presents the syntax and semantics of a novel type of hybrid
automaton (HA) with partial differential equation (PDE) dynamic, partial
differential hybrid automata (PDHA). In PDHA, we add a spatial domain $X$ and
harness a mathematic conception, partition, to help us formally define the
spatial relations. While classically the dynamics of HA are described by
ordinary differential equations (ODEs) and differential inclusions, PDHA is
capable of describing the behavior of cyber-physical systems (CPS) with
continuous dynamics that cannot be modelled using the canonical hybrid
systems’ framework. For the purposes of analyzing PDHA, we propose another
model called the discrete space partial differential hybrid automata (DSPDHA)
which handles discrete spatial domains using finite difference methods (FDM)
and this simple and intuitive approach reduces the PDHA into HA with ODE
systems. We conclude with two illustrative examples in order to exhibit the
nature of PDHA and DSPDHA.

###### keywords:

Hybrid Automata, Cyber-Physical Systems, Partial Differential Equations

##  1 Introduction

Cyber-Physical Systems have the potential to revolutionize the development of
technology worldwide, and in recent years, numerous researchers and companies
have invested significant time and money into ensuring that these systems will
realize their economic and societal potential [1]. However, since CPS
fundamentally integrate computational and physical processes, there are unique
challenges in designing and analyzing these systems. In fact, the functional
correctness of CPS relies deeply on the dynamics of their physical environment
and the discrete control decisions of their computational units. Within hybrid
systems, the framework of HA has demonstrated considerable utility in
capturing the complex interactions between the discrete and continuous parts
of a CPS. Additionally, it allows for a formal analysis of the safety and
reliability of CPS [2]. However, this modelling framework has catered to
systems with dynamics that can be described by ODEs, and hardly any attention
has been paid to systems with dynamics described by PDEs [3].

Meanwhile, safety of certain CPS relies on reachable set/state estimation
results that are based on Lyapunov functions analogous to stability [4, 5, 6,
7, 8, 9, 10] and reachability analysis of dynamical systems [11, 12],
certainly have potentials to be further extended to safety verification. One
can study the stability of switched systems, a switched system is composed of
a family of continuous or discrete-time subsystems along with a switching rule
governing the switching between the subsystems, with the help of the given
switching rules described by a prescribed state space partitioning [13, 14,
15] or some known constraints on switching sequence such as dwell time [16,
17] or average dwell time [18, 19] restrictions.

PDEs are accomplished at describing a wide range of phenomena such as fluid
dynamics and quantum mechanics that cannot be adequately described by ODEs
[20, 21, 22]. As an example, a typical application for PDEs is the modelling
of congestion in highway networks [23], and one popular model for highway
control is the Lighthill-Whitham-Richards (LWR) model [24, 25]. Within this
context, the PDEs evolve in an infinite dimensional space and must be
discretized for computational purposes. In our approach, we seek to extend the
existing framework from ordinary differential equations to partial
differential equations. However, this extension is non-trivial since the
internal structure of HA with PDEs is inherently more complicated due to the
fact that switching and jump conditions cannot be easily specified. An in-
depth discussion of these complexities, along with a discussion of three types
of switching conditions, can be found in the following paper by [26].

While the hybrid automata theory for ordinary differential equations (ODEs)
has been extensively studied (e.g., see [27, 28]), the theory for partial
differential equations (PDEs) is still in the stage of case study [29, 30, 31,
32]. The main challenges in this area can be attributed to two factors:

  1. (1)

The dynamics of automata involve switching due to known constraints, which
gives rise to the so-called _free boundary problem_. This problem entails
tracking the interface between different stages. In the context of PDEs,
analyzing and numerically solving the free boundary is highly challenging
(e.g., see [33, 34, 35, 36, 37, 38, 39]).

  2. (2)

Unlike ODEs, PDEs incorporate various types of boundary conditions.
Determining suitable boundary conditions for the partition is a complex task
that poses numerical challenges.

Therefore, in this article, we present a novel approach to address the hybrid
automata problem with partial differential modelling. Our approach aims to
reduce the PDE problem to a manageable ODE hybrid automaton by employing a
standard numerical discretization technique known as the _finite difference
method_.

##  2 Running Examples

Before illustrating the main ideas of our framework, we use two running
examples throughout the paper. The components of these running examples are
depicted in Figures 1 and 2. The heater model consists of three devices: (i) a
rod that can be heated using a gas burner from anywhere, (ii) a long gas
burner that can be turned on or off partially in any region, and (iii) a
thermometer that monitors the temperature of the rod at every location and
periodically issues signals when the temperature of the rod is above or below
certain a threshold. The goal is to design a control policy that maintains the
temperature of the rod within a given range.

The second model we consider is a traffic model that was originally proposed
in [26]. The system consists of a highway segment in which vehicles flow in
and out. Vehicles maintain a high speed when the traffic flow density is below
a given critical density and when the density exceeds the critical threshold,
the speed of the traffic wave and the overall flow capacity decrease.

###  2.1 Heater Model

Figure 1: Diagram for heater model.

We first describe the behavior of the temperature of the rod. When the gas
burner is OFF, the temperature of the rod, denoted by the variable $u$,
decreases according to the following PDE: $u(x,t)_{t}-\alpha u(x,t)_{xx}=0$
where $\alpha$ is the thermal diffusivity. The thermal diffusivity measures
the rate of heat transfer of a material from the hot side to the cold side.
The boundary conditions are $u(0,t)=0$ and $u(L,t)=0$, which denote that at
the location $x=0$ and $x=L$ the temperature is fixed to be $0$, and heat is
absorbed. $X$ denotes the space coordinate and $t$ denotes time. This law,
however, is only true when the temperature of the corresponding position on
the rod is greater than 0.7. When the heater is OFF, and the temperature of a
position on the rod is below 0.4, the heater at that position will be turned
on. The heater function is defined as $f(x)=-\frac{x}{L}+1$. The maximum of
the heater function appears at $x=0$ and the minimum is $0$ at $x=L$. During
the heater ON mode, the temperature is governed by the equation
$u(x,t)_{t}-\alpha u(x,t)_{xx}=f(x)$ where $f(x)$ is the function defined
above. As one can see from the description of the evolution of the
temperature, the system is not purely continuous. The system can switch from
one mode to another by turning the heater on and off at a specific location on
the rod.

###  2.2 Traffic Flow Model

Figure 2: Diagram for traffic model.

The traffic model describes how traffic conditions may behave on a given
highway. In free flow mode, which means the density is less than a specified
critical density $\rho_{c}$, the density function is given by the following
equation $u(x,t)_{t}+v_{1}u(x,t)_{x}=0$, where $v_{1}$ is always a positive
number and denotes that the traffic flow propagates forward. However, if the
traffic density achieves $\rho_{c}$, the system transitions into a high-
density congestion mode. In this mode, the governing equation is described by
$u(x,t)_{t}+v_{2}u(x,t)_{x}=0$, where $v_{2}$ is always a negative number and
denotes that traffic congestion always moves backwards and propagates
upstream. As an example, one of the causes of congestion may be a result of
merging slow and fast-moving traffic, resulting in a high-density traffic
flow. In this model, we can frequently switch between a free-flowing mode and
a congestion mode, and as a result, a more powerful hybrid framework is needed
to formalize these kinds of system behavior.

Additionally, the two models we have outlined present a mixture of space and
time variables and are therefore quite complicated. In the following sections,
we present a framework that is able to capture such a mixture of discrete and
continuous behaviors, where PDEs describe the temporal and spatial dynamics.

##  3 Partial Differential Hybrid Automata

###  3.1 Transitions, Trajectories and Executions

Due to the properties of PDEs, the switching structure is more involved than
in the case of ODEs [26]. One highway congestion alleviation model in [23]
considers $N$ connected segments, where each segment is governed by an
independent LWR PDE [24] with one side boundary condition. Each segment
affects the boundary condition of the preceding segment and serves as an input
function to the PDE. Additionally, the system is allowed to switch to another
mode that incorporates a speed limit. One control approach for transport
systems [40] proposes rules for switching based on criteria of minimizing a
cost function. We outline two specific structures that are of interest to our
framework:

  * 1.

_Switching PDEs in time on the full spatial domain_. This situation is
portrayed in Figure 3 (left) and is the PDE counterpart of hybrid systems as
defined in [41], where a game theory approach is used to determine when mode
switching occurs. Boundary condition switching has been investigated in
highway traffic applications in [42]. PDE switching in time appears in [40]
and in [23] and the latter one contains switching between modes in each
highway segment.

  * 2.

_Switching PDEs on subsets of the time-space domain_. This is illustrated in
Figure 3 (right). Examples include the LWR PDE, in [23] where each highway
segment is coupled with a boundary condition at the starting point of itself.
This also appears in [24], where the LWR with triangular flux function can be
decomposed into two modes (two one-dimensional wave equations) resulting in a
partition of the $(x,t)$ space in regions with forward travelling waves, and
regions with backward travelling waves.

Figure 3: Switching cases for two scenarios, full domain switching on left and
partial domain switching on right. BC denotes boundary conditions and IC
denotes initial conditions. $x$ axis denotes the spatial domain and $y$ axis
denotes time.

In order to describe the partial domain switching case in Figure 3 (right), it
is useful to partition the whole domain into several parts and assign each one
a corresponding mode. One possible solution is to use the union of disjoint
domains to represent the region governed by specific modes. For example, the
heat equation $u_{t}-u_{xx}=0$ with $\alpha=1$ (mode 1) and without heat
source can cover domain $[0,0.4)$. The equation $u_{t}-u_{xx}=f(x)$ with
external source (mode 2) occupies domain $[0.4,1]$.

Based on this idea, the main challenge is how to formalize the particular
structure of the domain occupying behavior. One approach is to associate the
union operator with the modes of the system. Thus, the system mode $q$ can be
described as a composition of multiple modes $\cup q_{i}$, where each mode
specifies the domain it occupies. Like in $q_{1}$, $u_{t}-u_{xx}=0$ when
$x\in\mathcal{D}_{1}$ and in $q_{2}$, $u_{t}-u_{xx}=f(x)$ when
$x\in\mathcal{D}_{2}$, where $\mathcal{D}_{i}$ is the region occupied by
$q_{i}$. Thus, the space domain $X$ is composed of $\mathcal{D}_{1}$ and
$\mathcal{D}_{2}$.

This embodies our approach to represent the multiple mode occupation
phenomenon, and we refer to the multiple mode occupation as the changing
behavior of $\cup\mathcal{D}_{i}$. The remaining challenge is to how to
describe the moving behavior of the modes. This can be realized by changing
$\mathcal{D}_{i}$, together with its boundary condition. As the system
evolves, points satisfying a given condition will be moved from one mode to
another and cause $\mathcal{D}_{i}$ to grow or shrink. We call this point’s
moving behavior a _trajectory_. The evolution of $\mathcal{D}_{i}$ is not
easily depicted. It can be a function of time or a function of several other
complicated variables. Additionally, it might be impossible to predict
switching behavior due to the complexity exhibited by the PDE’s solution.

Based on the ideas discussed above, the concept of _spatial control mode_ is
given below.

######  Definition 1 (Spatial Control Mode).

Let $X\subseteq\mathbb{R}^{n}$ be a space domain. Let $Q$ be a finite set of
$m$ control modes, where each mode is denoted as $q_{i}$. A space control mode
consists of a union of $k~{}(k\leq m)$ control modes, where each mode covers
part of the space domain $X$. The spatial control mode is denoted by
$\tilde{q}$ where $\tilde{q}=\cup_{q_{i}\in Q}\\{q_{i}\\}\subseteq Q$ and the
region mode $q_{i}$ covers is denoted by $Dom(q_{i})$ and $Dom(\cdot)$ is a
set map $Dom(\cdot):Q\to 2^{X}$. Additionally,
$\cup_{i=1}^{k}\mathcal{D}_{i}=X$, where $\mathcal{D}_{i}=Dom(q_{i})$.

Now, according to our definition, $\tilde{q}$ is a subset of $Q$ and not just
an element in $Q$. We want to emphasize that the system could occupy several
control modes simultaneously, rather than stay at a single mode as defined in
classical hybrid automata. In order to accommodate $\tilde{q}$ and
$Dom(q_{i})$ and for the purposes of formalizing domain division, we rely on
_partition_ defined in Definition 2. One can see that
$\cup\\{\mathcal{D}_{i}\\}$ is a _partition_ of domain $X$ since each
$\mathcal{D}_{i}$ is nonempty, $\bigcup\\{\mathcal{D}_{i}\\}=X$ and
$\mathcal{D}_{i}\cap\mathcal{D}_{j}=\emptyset$ for $i\neq j$. For convenience,
we denote $p=\cup\\{\mathcal{D}_{i}\\}$ a specific _partition_ of $X$
consisting of $\mathcal{D}_{i}$s and denote $P=\cup\\{p\\}$ a set containing
all possible _partition_ s of domain $X$.

######  Definition 2 (Partition [43]).

A partition of a set $S$ is a set of nonempty subsets of $S$ such that every
element $x$ in $X$ is in exactly one of these subsets. Equivalently, a family
of sets $p$ is a partition of $X$ if and only if all the following conditions
hold:

  * 1.

The family $p$ does not contain the empty set (that is $\emptyset\notin p$).

  * 2.

The union of the sets in $p$ is equal to $X$ (that is $\cup_{a\in p}a=p$).

  * 3.

The intersection of any two distinct sets in $p$ is empty (that is ($\forall
a,b\in p$) $a\neq b\Rightarrow a\cap b=\emptyset$).

It is worth noting that the new PDE dynamic hybrid automaton needs a function
to describe its state value. The additional spatial variable requires us to
specify the values at different space locations while, in classical hybrid
automata, the system only has finite values since the system only considers
finite continuous state variables. The values of these state variables and
discrete modes can be determined as long as the time is fixed, and the system
is deterministic. In our model, for any time $t$, we regard that the PDE
solution $u(\cdot,t)$ lies in the state space $U=\mathbb{R}^{X}$. In other
words, for any given $x\in X$, $u(x,\cdot)$ represents a real-valued
trajectory.

After we obtain $\tilde{q}$, $p$ and $u(\cdot,t)$, the _state_ can be defined
now.

######  Definition 3 (State).

A state $s$ is a collection of variables that describes the current condition
of a PDE dynamic system. It consists of a _space control mode_ $\tilde{q}$, a
_partition_ $p$ of a domain $X$ and a real function $u(\cdot,t)$ defined on
$X$.

$\begin{split}&s=\tilde{q}\times p\times u(\cdot,t)\in 2^{Q}\times P\times
U\\\ \end{split}$ (1)

In Figure 3 (left), each mode occupies the whole space domain $X$ and the
system stays in only one mode. We have $q=\\{q_{i}\\},\mathcal{D}_{i}=X$,
$i=1,2,3$. In Figure 3 (right), PDE 1 (mode 1) and PDE 2 (modes 2) occupy the
whole domain $X$, $q=\\{q_{1}\cup q_{2}\\}$ and
$\mathcal{D}_{1}\cup\mathcal{D}_{2}=X$ at $t=0$. It is worth stressing the
differences between representing a state in PDE dynamic hybrid automata and
classical hybrid automata. For discrete modes, the combination of $\tilde{q}$
and $p$ replaces the single $q$ and describes the space occupation behavior.

Bearing the above in mind, the next step is to formalize the flow function.

######  Definition 4 (Flow).

A flow for a PDE dynamic hybrid automaton is of the form $2^{Q}\times P\times
U\rightarrow U$ which maps from one state to another as time evolves.

Similar to classical hybrid automata, PDE equations simulate the dynamics of
the system. The flow consists of a piecewise PDE equation and the
corresponding domain partition. A simple flow function for the heater example
can be formally represented as

$\begin{cases}u_{t}-u_{xx}=f(x,t;q),~{}&0<x<L,\quad 0<t<T,\quad q\in Q,\\\
u(0,t)=u(L,t)=0,&0\leq t\leq T,\\\ u(x,0)=u_{0}(x),&0\leq x\leq L.\end{cases}$

######  Definition 5 (Transition).

A transition in a PDE dynamic hybrid automaton is of the form $2^{Q}\times
P\times U\times E\rightarrow 2^{Q}\times P$ which maps the current mode and
partition to another. $E$ is a finite set of events.

######  Definition 6 (Reset).

A reset function for a PDE dynamic hybrid automaton is of the form
$2^{Q}\times P\times U\times E\rightarrow U$ which specifies how the value of
$u(x,t)$ changes when a transition takes place.

The ON mode, triggered by conditions defined in the set $E$, for example
(Figure 4), $u(x,t)\geq r_{1}$, then $q=q_{1}$ so that $f(x,t;q_{1})=f(x)$
while the OFF mode happens when $u(x,t)\leq r_{2}$, we set $q=q_{2}$, then
$f(x,t;q_{2})=0$.

###  3.2 Partial Differential Hybrid Automaton (PDHA)

With the above discussion in mind, we can now provide a formal definition of a
partial differential hybrid automaton.

######  Definition 7 (Partial Differential Hybrid Automaton (PDHA)).

A _partial differential hybrid automaton_ is a tuple $\langle
Q,E,P,X,U,Init,Inv,f,\phi,G,R\rangle$ where:

  * 1.

$Q$ is a set of finite $q_{i}$s that represents control modes.

  * 2.

$E$ is a finite set of events.

  * 3.

$X$ is a space domain and $X\subseteq\mathbb{R}^{n}$.

  * 4.

$P$ is a set of all partitions defined on domain $X$.

  * 5.

$U$ is a function space defined on domain $X$ and $U=\mathbb{R}^{X}$.

  * 6.

$Init$ is a set of initial states and $Init\subseteq 2^{Q}\times P\times U$.

  * 7.

$Inv$ is a set of invariants defined for each mode $q_{i}$.

  * 8.

$f:2^{Q}\times P\times U\to U$ is a flow function and $f$ has the form :

$\begin{cases}u_{t}=f_{1}(\Delta u,\nabla
u,x,t),~{}~{}x\in\mathcal{D}_{1},~{}~{}q=q_{1}\\\ u_{t}=f_{2}(\Delta u,\nabla
u,x,t),~{}~{}x\in\mathcal{D}_{2},~{}~{}q=q_{2}\\\ ...\\\ u_{t}=f_{k}(\Delta
u,\nabla u,x,t),~{}~{}x\in\mathcal{D}_{k},~{}~{}q=q_{k}.\\\ \end{cases}$

where $f_{i},i\in\\{1,2,...,k\\}$, is the continuous segment in $f$, $\Delta$
is the Laplacian, $\nabla$ is the gradient, and
$\mathcal{D}_{i},i\in\\{1,2,...,k\\}$ is the domain covered by $q_{i}$.

  * 9.

$\phi:2^{Q}\times P\times U\times E\rightarrow 2^{Q}\times P$ is a transition
map.

  * 10.

$G$ is a set defining guard condition, $G\subseteq 2^{Q}\times P\times
2^{Q}\times P\times U$.

  * 11.

$R:2^{Q}\times P\times U\times E\rightarrow U$ is a reset function.

In our framework, each mode contains only one PDE instead of a system of
equations as in classical hybrid automata. Boundary conditions must not be
violated and can be treated as a kind of _invariant_. They are imposed on the
boundary of $X$ and act like constraints within the mode. Additionally, they
are forced to be satisfied even during mode discrete transitions.

Figure 4: Heater PDHA corresponding to the system in Figure 1. Figure 5:
Traffic PDHA corresponding to the system in Figure 2.

Revisiting the examples outlined at the very beginning, we construct two
models to illustrate the idea of PDHA in Figures 1 and 2. In each model, the
system is composed of two modes and each mode is governed by a PDE, the given
boundary conditions, and the initial condition. In the heater model, we have
$f_{i}(\Delta u,\nabla u,x,t)=\Delta u+f(x,t;q_{i})$.

The continuous trajectory is realized by moving a point satisfying a guard
condition $G$ to another mode. In the heater model, a point in the mode ON
where the temperature exceeds the threshold will be transferred to the mode
OFF, meaning the heater located at this point is turned off while the other
areas remain unchanged. At the same time, as the temperature at some points
drops below some given bound, the heater at that location is turned on and the
point at mode OFF will be moved to mode ON.

The same rule applies to the traffic model as well. The points in the free
flow mode satisfying the guard condition $G_{1}$ will be moved to a congestion
mode, and points in the congestion mode satisfying $G_{2}$ will be moved to
the free flow mode.

##  4 Discrete Space Partial Differential Hybrid Automaton

In this section, we describe some core steps in deriving DSPDHA. First, we
define a discretization scheme and use it to discretize a PDHA to construct
its “discrete” model for analysis. Second, using this discretization scheme,
we define a discrete PDHA that is related to the original PDHA via a
“discretization relation” corresponding to the scheme $\mathcal{R}$.

###  4.1 Discretization Scheme and Discretization Relation

A discrete treatment of PDEs requires the use of new tools to realize the
functions we need. One of the most widely used sets of methods is called
finite difference methods (FDMs). Generally speaking, FDMs are a family of
numerical approaches for solving differential equations by replacing them with
an approximation using difference equations. Combining FDMs and PDHA produces
the following definition:

######  Definition 8 (Discretization Scheme).

A discretization scheme is a numerical scheme to discretize a continuous
partial differential equation into a set of algebraic equations (full-
discretization scheme) or ordinary differential equations (semi-discretization
scheme).

We present several schemes below to demonstrate how this technique
approximates spatial derivatives.

######  Example 4.1 (Finite Difference Method Discretization Scheme).

A common example is shown for the heat equation using the central difference
scheme:

$\begin{split}u(i\times h,t)_{xx}=\frac{u((i-1)\times h,t)-2u(i\times
h,t)+u((i+1)\times h,t)}{{h}^{2}}+O(h^{2}),\end{split}$ (2)

where the scheme is based on a uniform mesh, $h$ is the grid size,
$h=x_{i+1}-x_{i}$, $\\{x_{1},x_{2},x_{3},...,x_{n}\\}$ is a list of locations
where the mesh points sit, and these points are the same ones defined in
$p_{d}$. Additionally, $u(i\times h,t)$ denotes the value at the $i^{th}$
position given time $t$ and the respective derivative is approximated using
itself and the two adjacent values. The proof is based on using Taylor’s
expansion with error $O(h^{2})$.

After applying (2) and dropping the redundant part $O(h^{2})$, the heat
equation becomes

$\begin{split}&\dot{u_{i}}(t)\approx\frac{1}{{h}^{2}}(u_{i-1}(t)-2u_{i}(t)+u_{i+1}(t))+f(i\times
h,t),~{}~{}i=1,2,\cdots,n.\end{split}$ (3)

We replace $u(i\times h,t)$ by $u_{i}(t)$ since the derivative with respect to
space has been removed. Thus, $\dot{u}_{i}(t)$ is used to represent the time
derivative at the grid point $i\times h$, and $f(i\times h,t)$ represents the
input function valued at the same location.

Once the scheme has been chosen, the relation between our models can be
described by the following definition.

######  Definition 9 (Discretization Relation).

If the model $A$ is obtained from the model $B$ via discretization scheme
$\mathcal{R}$, we say that the model $A$ relates to the model $B$ via
discretization scheme $\mathcal{R}$, which is denoted by:
$A\preceq^{\mathcal{R}}B$.

###  4.2 Discrete Space Partial Differential Hybrid Automaton

Using a discretization scheme, we obtain discrete models of the state,
transition, flow and reset function of the original PHDA. These discrete
models are defined below.

Figure 6: Irregular discretization on domain $X$, the left diagram shows the
partition of $X$ and the right diagram shows how discretization is used on the
domain $X$. The black dots represent the points chosen in $X_{d}$ and are
connected through dash lines. These points can be on the boundary or inside
the region.

######  Definition 10 (Discrete Domain).

Let $X$ be a domain and $X\subseteq\mathbb{R}^{n}$, a discrete domain $X_{d}$
of $X$ is a set of distinct points obtained from $X$ by a discretization
scheme $\mathcal{\mathcal{R}}$: $X_{d}=\bigcup_{i=1}^{m}\\{x_{i}\\}$,
$x_{i}\in X$ and $m$ is the number of points. We say
$X_{d}\preceq^{\mathcal{R}}X$.

######  Example 4.2 (Discrete Domain of Heater Model).

Consider the heat equation defined on domain $X=[0,10]$. One possible
corresponding discrete domain $X_{d}$ is $\\{0,1,2,3,4,5,6,7,8,9,10\\}$.

######  Definition 11 (Discrete Partition).

Let $Q$ be a set of modes, $P$ is the set of all partitions on $X$ and
$X_{d}\preceq^{\mathcal{R}}X$. A discrete partition $p_{d}\in Q^{m}$ is a set
of values, and each value is associated with a point $x_{i}\in X_{d}$. The set
of all possible $p_{d}$s is denoted by $P_{d}=Q^{m}$ and
$P_{d}\preceq^{\mathcal{R}}P$.

In contrast to the continuous domain hybrid automaton which uses
$\tilde{q}\times p$ to describe the current mode that the system occupies, a
discrete partition combines the two notations and simplifies the expression.

######  Example 4.3 (Discrete Partition of Heater Model).

Consider the model with $\ q_{1}=$ OFF, $\ q_{2}=$ ON and
$X_{d}=\\{0,1,2,3,4,5\\}$. Then $\tilde{q}=\\{q_{1},q_{2}\\}$,
$\mathcal{D}_{1}=[0,3]$ and $\mathcal{D}_{2}=(3,5]$ can be expressed as
$\\{q_{1},q_{1},q_{1},q_{1},q_{2},q_{2}\\}$.

######  Definition 12 (Discrete State).

A discrete state $s_{d}$ is an ordered pair $(p_{d},u_{d})$ where $p_{d}\in
P_{d}\preceq^{\mathcal{R}}P$ is a discrete partition on
$X_{d}\preceq^{\mathcal{R}}X$ and $u_{d}\in\mathbb{R}^{m}$ is a list of real
values. We denote the set of all possible $s_{d}$s by $S_{d}$ and say
$S_{d}\preceq^{\mathcal{R}}S$ where $S$ is the set of states defined in PDHA.

A discrete state gives the whole picture of the system by combining a discrete
partition and state values.

######  Example 4.4 (Discrete State of Heater Model).

One discrete state can be in the form
$\\{\\{q_{1},q_{1},q_{1},q_{1},q_{2},q_{2}\\},\\\
\\{0.6,0.6,0.5,0.6,0.7,0.8\\}\\}$, where $q_{1},q_{2}$ are the modes and the
succeeding numbers are the temperatures at each node.

Everything listed above leads us to _discrete flow_.

######  Definition 13 (Discrete Flow).

Let $f$ be a flow function, $f_{d}$ is the set of discrete flow functions such
that the spatial derivative of $f$ is approximated using $\mathcal{R}$. We say
$f_{d}\preceq^{\mathcal{R}}f$.

######  Example 4.5 (Discrete Flow of Heater Model).

Consider the heater example again,

$\begin{cases}u_{t}-u_{xx}=f(x,t),\quad&0<t<T,\quad 0<x<L,\\\
u(0,t)=u(L,t)=0,\quad&0\leq t\leq T.\end{cases}$

The spatial derivative $u_{xx}$ is approximated by a FDM centred difference
scheme based on a uniform mesh of step size $\Delta x$. We obtain a system of
ODEs: In place of $u(t,i\Delta x)$, we obtain an ODE system for $u_{i}(t)$,
$i=1,\cdots,m$, $(m+1)\Delta x=L$:

$\dot{u}_{i}(t)=\frac{u_{i-1}-2u_{i}+u_{i+1}}{\Delta x^{2}}+f(t,i\Delta x),$

where $u_{0}=u_{1},u_{m+1}=u_{m}$ due to the boundary condition. We would like
to remark that the convergence of FDM is due to the Lax–Richtmyer theorem
[44].

######  Definition 14 (Discrete Transition).

A discrete transition $\phi_{d}$ of a DSPDHA is of the form $P_{d}\times
U_{d}\times E\rightarrow P_{d}$ which maps a current discrete partition to
another. We say $\phi_{d}\preceq^{\mathcal{R}}\phi$ where $\phi$ is the
transition defined in the original $PDHA$ and $\mathcal{R}$ is the
discretization scheme.

######  Example 4.6 (Discrete Transition of heater model).

In order to illustrate the idea of a discrete transition, we make a simple
modification of the previous example:

$\begin{cases}\dot{u}_{1}=\displaystyle\frac{-2u_{1}+u_{2}}{h^{2}},\\\
\dot{u}_{2}=\displaystyle\frac{u_{1}-2u_{2}+u_{3}}{h^{2}},\\\ \quad\vdots\\\
\displaystyle\dot{u}_{m}=\frac{u_{m-1}-2u_{m}}{h^{2}}.\end{cases}$

$\xrightarrow{e^{{}^{\prime}}}\begin{cases}\dot{u}_{1}=\displaystyle\frac{-2u_{1}+u_{2}}{h^{2}},~{}~{}\\\
\dot{u}_{2}=\displaystyle\frac{u_{1}-2u_{2}+u_{3}}{h^{2}}+f(2h,t),~{}~{}\\\
\quad\vdots\\\
\displaystyle\dot{u}_{m}=\frac{u_{m-1}-2u_{m}}{h^{2}}+f(mh,t).\end{cases}$

A transition to the mode ON at location $x_{1}$ and $x_{2}$ occurs because
event $e$ takes place. Thus, we can write the transition function

$\phi_{d}(p_{d,1};u_{d};e)=\begin{cases}p_{d,2},~{}~{}e=e^{{}^{\prime}},\\\
p_{d,1},~{}~{}otherwise.\\\ \end{cases}$ (4)

where $p_{d,1}=\\{q_{1},q_{1},q_{2},...,q_{2}\\}$,
$p_{d,2}=\\{q_{2},q_{2},q_{2},...,q_{2}\\}$, $q_{1}$ represents mode OFF and
$q_{2}$ represents mode ON.

######  Definition 15 (Discrete Reset).

A discrete reset function $R_{d}$ of a DSPDHA is of the form $P_{d}\times
U_{d}\times E\rightarrow U_{d}$ which specifies how a value of $u_{d}$ changes
to a new value when a transition takes place. We say
$R_{d}\preceq^{\mathcal{R}}R$ where $R$ on the right is the reset function in
original $PDHA$.

######  Definition 16 (Discrete Space Partial Differential Hybrid Automaton
(DSPDHA)).

A _discrete space partial differential hybrid automaton_ is a tuple $\langle
Q,E,P_{d},X_{d},U,Init,Inv,f_{d},\phi_{d},G,R_{d}\rangle$ where:

  * 1.

$Q$ is a set of finite modes;

  * 2.

$E$ is a set of finite events;

  * 3.

$X_{d}$ is a set of $m$ points;

  * 4.

$P_{d}$ is a set of values defined on domain $X_{d}$, $P_{d}\in Q^{m}$;

  * 5.

$U_{d}$ is a set of discrete values defined on $X_{d}$,
$U_{d}=\mathbb{R}^{m}$;

  * 6.

$Init$ is a set of initial states, $Init\subseteq P_{d}\times U_{d}$;

  * 7.

$Inv$ is a set of invariants defined for each mode $q_{i}\in Q$;

  * 8.

$f_{d}:P_{d}\times U_{d}\to U_{d}$ is a set of discrete flow functions and
$f_{d}$ have the form :

$\begin{cases}\dot{u}_{1}=f_{1}(u_{1},u_{2},...,u_{m},t),\\\
\dot{u}_{2}=f_{2}(u_{1},u_{2},...,u_{m},t),\\\ ...\\\
\dot{u}_{m}=f_{m}(u_{1},u_{2},...,u_{m},t).\\\ \end{cases}$ (5)

where $\dot{u}_{i}$ denotes time derivative of $u_{i}$;

  * 9.

$\phi_{d}:P_{d}\times U_{d}\times E\rightarrow P_{d}$ is a transition
function;

  * 10.

$G$ is a set defining guard condition, $G\subseteq P_{d}\times P_{d}\times
U_{d}$;

  * 11.

$R_{d}:P_{d}\times U_{d}\times E\rightarrow U_{d}$ is a reset function.

A key observation is $DPH\preceq^{\mathcal{R}}PH$ if the discrete space
partial differential hybrid automaton $DPH$ is obtained from a partial
differential hybrid automaton $PH$ through $\mathcal{R}$.

The DSPHDA provides us with a set of properties that can easily be formalized
and stated. Additionally, similar concepts that appear in HA are outlined
below.

######  Definition 17 (Hybrid Time Trajectory).

A hybrid time trajectory $\tau=\\{I_{i}\\}_{i=0}^{N}$ is a finite or infinite
sequence of intervals of the real line, such that

  * 1.

$I_{i}=[\tau_{i},\tau_{i}^{{}^{\prime}}]$ for $i<N$;

  * 2.

if $N<\infty$, then either $I_{N}=[\tau_{N},\tau_{N}^{{}^{\prime}}]$, or
$I_{N}=[\tau_{N},\tau_{N}^{{}^{\prime}})$;

  * 3.

for all $i$, $\tau_{i}\leq\tau_{i}^{{}^{\prime}}=\tau_{i+1}$.

where $\tau_{i}^{{}^{\prime}}$ are the time when _discrete transition_ takes
place.

Now that we have defined the syntax of DSPDHA, we define the semantics in
terms of _executions_.

######  Definition 18 (Execution).

An _execution_ of a DSPDHA is a collection $\chi=(\tau,p_{d},u_{d})$
satisfying

  * 1.

Initial Condition: $(p_{d}(\tau_{0}),u_{d}(\tau_{0}))\in$ Init;

  * 2.

Continuous Evolution: for all $i$ with $\tau_{i}<\tau_{i}^{{}^{\prime}}$,
$p_{d}$ is a constant, $u_{d}$ is a solution to the ODEs (5) over
$[\tau_{i},\tau_{i}^{{}^{\prime}}]$ and for all
$t\in[\tau_{i},\tau_{i}^{{}^{\prime}})$, $u_{d}(t)\in I$;

  * 3.

Discrete Evolution: for all $i$, $(p_{d}(\tau_{i+1}),u_{d}(\tau_{i+1}))\in
R(p_{d}(\tau_{i}^{{}^{\prime}}),u_{d}(\tau_{i}^{{}^{\prime}}))$.

An execution $\chi=(\tau,p_{d},u_{d})$ is called _finite_ if $\chi$ is a
finite sequence ending with a closed interval, _infinite_ if $\tau$ is either
an infinite sequence, or if
$\sum_{i=0}^{\infty}(\tau_{i}^{{}^{\prime}}-\tau_{i})=\infty$, and Zeno if it
is _infinite_ but
$\sum_{i=0}^{\infty}(\tau_{i}^{{}^{\prime}}-\tau_{i})<\infty$.

######  Definition 19 (Zeno Execution).

An execution $\chi$ is Zeno if

$\lim_{i\rightarrow\infty}\tau_{i}-\tau_{0}=\sum_{i=0}^{\infty}(\tau_{i}^{{}^{\prime}}-\tau_{i})=\tau_{\infty}<\infty$
(6)

Here $\tau_{\infty}$ is called the Zeno time.

We use $\mathcal{E}_{DPH}(p_{d,0},u_{d,0})$ to denote the set of all
executions of DSPDHA with initial condition $(p_{d,0},u_{d,0})\in Init$,
$\mathcal{E}_{DPH}^{*}(p_{d,0},u_{d,0})$ to denote the set of all finite
executions, $\mathcal{E}_{DPH}^{\infty}(p_{d,0},u_{d,0})$ to denote the set of
all infinite executions, and $\mathcal{E}_{DPH}$ to denote the union of
$\mathcal{E}_{DPH}(p_{d,0},u_{d,0})$ over all $(p_{d,0},u_{d,0})\in Init$.

######  Definition 20 (Zeno Discrete Space Partial Differential Hybrid
Automaton).

A discrete space partial differential hybrid automaton DPH is Zeno if there
exists $(p_{d,0},u_{d,0})\in Init$ such that all executions in
$\mathcal{E}_{DPH}^{\infty}(p_{d,0},u_{d,0})$ are Zeno.

$\lim_{i\rightarrow\infty}\tau_{i}-\tau_{0}=\sum_{i=0}^{\infty}(\tau_{i}^{{}^{\prime}}-\tau_{i})=\tau_{\infty}<\infty$
(7)

Here $\tau_{\infty}$ is called the Zeno time.

The set of states reachable by a DSPDHA, $Reach_{DPH}$, is defined as

$\begin{multlined}Reach_{DPH}=\\{(\hat{p_{d}},\hat{u_{d}})\in P_{d}\times
U_{d}:\exists(\tau,p_{d},u_{d})\in\mathcal{E}_{DPH}^{*},(p_{d}(N),u_{d}(\tau_{N}^{{}^{\prime}}))=(\hat{p_{d}},\hat{u_{d}})\\}.\end{multlined}Reach_{DPH}=\\{(\hat{p_{d}},\hat{u_{d}})\in
P_{d}\times
U_{d}:\exists(\tau,p_{d},u_{d})\in\mathcal{E}_{DPH}^{*},(p_{d}(N),u_{d}(\tau_{N}^{{}^{\prime}}))=(\hat{p_{d}},\hat{u_{d}})\\}.$
(8)

where $\tau=\\{[\tau_{i},\tau_{i}^{{}^{\prime}}]\\}_{i=0}^{N}$.

######  Definition 21 (Nonblocking).

A DSPDHA is called nonblocking if
$\mathcal{E}_{DPH}^{\infty}(p_{d,0},u_{d,0})$ is nonempty at all
$(p_{d,0},u_{d,0})\in Init$.

######  Definition 22 (Deterministic).

A DSPDHA is called deterministic if $\mathcal{E}_{DPH}^{*}(p_{d,0},u_{d,0})$
contains at most one element for all $(p_{d,0},u_{d,0})\in Init$.

More definitions about DSPDHA are similar to those in the classical HA theory,
and we omit them here for the simplicity of the presentation.

###  4.3 Relation to Classical Hybrid Automaton

In this section, we explore the relations between classical hybrid automata,
DSPDHA and PDHA. The central basis of introducing PDHA is extending HA with
ODE dynamics to discretize PDE dynamics. To achieve this goal, some
adjustments need to be made to accommodate the new framework within the
classical hybrid automata scheme. It is our hope, that after these changes,
the properties that hold for HA will hold for PDHA as well. This is the basis
for the motivation to add an intermediate level (DSPDHA) lying between PDHA
and HA, which captures the idea of PDHA and also stays close to classical HA.
Using this framework, we make comparisons and illustrate useful results in the
form of theorems.

In PDHA, we use space control modes and partitions $\tilde{q}\times p$ to
replace a discrete mode $q$, a state function $\varphi(x)$ to replace state
variables $X$. The weakness of this scheme is determining executions and
transitions because $\tilde{q}\times p$ evolves continuously. DSPDHA overcomes
these shortcomings by introducing a discrete state partition, $p_{d}$ which
functions similarly to $q$ in HA. Along the same lines, a discrete flow
function obtained from PDHA by FDM is essentially the same as a HA flow
function. This allows us to assert some PDE system properties where we cannot
otherwise reason with certainty due to a lack of information. We lay out
several points below to illustrate how these connections are built.

Figure 7: PDHA, DSPDHA and HA relations.

  1. (1)

_Any DSPDHA is a HA if $p_{d}$ has identical elements._ Based on the knowledge
that elements in $p_{d}$ represent the modes where each location resides,
identical elements indicate all the locations are assigned to the same modes
and the system stays at a single mode. Therefore, the given DSPDHA is a HA.
Thus, the general dynamical properties of HA, for instance, the existence,
uniqueness, continuous dependence, reachability, stability and invariant sets
follows. (See [45]). On the other, the DSPDHA inherits the physical feature
(like diffusion) from the PDE model, which we demonstrate in the heat model
below.

  2. (2)

_If the order of the time derivative of the PDE considered in a PDHA is $1$,
the number of points $m$, in a discrete domain $X_{d}$ is equivalent to the
size of flow functions in the corresponding DSPDHA._ According to Definition
13, the discretization is made on each discrete point in $X_{d}$. As a result,
we have $m$ equations eventually.

  3. (3)

_If the order of the highest time derivative of a PDE is $n$, then the PDE can
be reduced to a system of $n$ PDEs with a $1^{st}$ order time derivative._ We
begin the proof by a change of variables. Let us replace the $k^{st}$ order
time derivative of $u$ by $v_{k}$ and add a new equation to the system once
the replacement is done. In the end, we obtain a system of equations in the
form below.

$\begin{cases}\dot{u}=v_{1},\\\ \dot{v}_{1}=v_{2},\\\ \dot{v}_{2}=v_{3},\\\
...,\\\ \dot{v}_{n-2}=v_{n-1},\\\
\dot{v}_{n-1}=f(u,u_{x},u_{xx},...,t).\end{cases}$ (9)

where the original equation is $u^{(n)}=f(u,u_{x},u_{xx},...,t)$ and $u^{(n)}$
is its $n^{th}$ time derivative. For example, we can deal with the wave
equation $u_{tt}-u_{xx}=0$.

  4. (4)

_If the order of time derivative of the PDE considered in a PDHA is $n$ and
the number of points in discrete domain $X_{d}$ is $m$, the size of flow
functions in the corresponding DSPDHA is $n\cdot m$._ Since $m$ determines the
number of mesh points and each point is associated with an ODE ($1^{st}$ order
PDE after spatial discretization), $m$ equals the dimension of the system of
ODEs which is the flow function.

Besides investigating the relation and distinction between models above, an
interesting observation which occurs in classical hybrid automata are
discontinuity issues, especially under PDE dynamics. [40] discusses the
propagation of discontinuities when the system switches mode. They are
numerous reasons why discontinuities occur. For the transport equation with a
nonlinear flux function, there does not always exist a smooth solution, and a
weak solution has to be constructed to handle a shock or rarefaction wave
[46]. Jump discontinuities for hyperbolic system are discussed in [47].

The situation discussed in [40] is likely to happen if the discrete transition
takes place in our framework. Consider a segment of road governed by a
transport equation and the model is $u_{t}+u_{x}=0$. Supposing the switching
is triggered, and a new model $u_{t}+2u_{x}=0$ is introduced, the latter model
which involves fast wave speed will push the front flow to move fast, and the
traffic will start to accumulate at the boundary of the road which directly
leads to a discontinuity.

##  5 Experiments on Running Examples

The heater and traffic examples are formalized as DSPDHA and analyzed in this
section. 111Code for the experiments is available at
https://drive.google.com/drive/folders/1qnpwlU9WdVNjYm8lsZOjAqFIQhGhH0ME?usp=sharing

#### Heater Model.

As illustrated above, the first example is the bronze rod with two isolated
ends. The heater provides heat to the rod and can be partially turned on and
off at any time once the temperature reaches the given thresholds. For the
input function, a linear increment function is considered with a maximum value
appearing on the left and a minimum value appearing value on the right. The
diagram of the model is in Figure 8.

Figure 8: PDHA diagram for the heater model analyzed. The left circle
indicates the ON mode and the right circle indicates the OFF mode. The guard
conditions are specified as greater equal than $0.7$ or less equal than $0.4$.
The initial condition is $0.2$ for everywhere.

(a) $\Delta x=1$

(b) $\Delta x=2$

Figure 9: Simulation results of heater model at $x=2$. The heater at location
$x=2$ is turned on and off repeatedly. The two subfigures use different
discretization sizes.

(a) $\Delta x=1$

(b) $\Delta x=2$

Figure 10: Simulation results of heater model at $t=9$. Temperatures at the
boundaries remain $0$. The two subfigures use different discretization sizes.

The idea of _discrete partitions_ is illustrated in this example, and $9$
points are chosen to describe the temperature along the rod. A point whose
value is greater than 0.7 will be moved to mode OFF and be moved back to ON as
the value drops below 0.4. The initial temperature is $0.2$ everywhere on the
rod, and the input function for mode ON is $f_{1}(x)=-0.1x+1$ and $0$ for mode
OFF. Since we have the boundary condition $u(0,t)=0$ and $u(L,t)=0$, the two
values, $u(x_{1},t)$ and $u(x_{n-1},t)$, will decrease rapidly due to the heat
diffusion effect [20]. Additionally, the input function decreases as $x$
increases, therefore the heating effect near the boundary $x=L$ will be
trivial, and the heater remains on. We discretize the domain and assign each
mesh point a heater. The center difference scheme is used to approximate the
space derivative and the forward scheme is used to approximate the time
derivative.

Mathematically speaking, we can see even though the discretization reduces the
model in HA for ODE, in the following analysis we can see the dynamic of the
solutions is consistent with the diffusion feature of the PDE model: consider
the following ODE system

$\left\\{\begin{array}[]{ll}\displaystyle\frac{du_{i}}{dt}=u_{i-1}-2u_{i}+u_{i+1}+(10-i)&\text{when
}u_{i}\leq 0.4,\\\
\displaystyle\frac{du_{i}}{dt}=u_{i-1}-2u_{i}+u_{i+1}&\text{when }u_{i}\geq
0.7,\end{array}\right.$ (10)

where $i=1,2,\cdots,9$ and $u_{0}=u_{10}=0$. Initially, we have
$u_{i}(0)=0.2$, (10) is an ODE system with constant coefficients, hence the
_existence, uniqueness_ and _continuous dependence_ follows from the standard
ODE theory. Furthermore, it is easy to see that

$\frac{du_{i}}{dt}\Big{|}_{t=0}=-i+10,\quad i=1,2,\cdots,9,$

in other words, $u_{i}$ is increasing initially since the heat source is
turned ON. If there are some $u_{i}$ hits the threshold value $0.7$, we may
pick the maximum value, say $u_{i}$, then since the heat source is turned OFF,
we have

$\frac{du_{i}}{dt}=u_{i-1}-2u_{i}+u_{i+1}\leq 0,$

where we use the fact that $u_{i}\geq u_{i-1}$, and $u_{i}\geq u_{i+1}$. This
implies that $u_{i}$ starts to decrease. For locations that are away from the
boundary, if the value falls into $0.4$, we pick the minimum value, then we
have that

$\frac{du_{i}}{dt}=(u_{i-1}-2u_{i}+u_{i+1})+10-i\geq 10-i>0,$

where we use the fact that $u_{i}\leq u_{i-1}$ and $u_{i}\leq u_{i+1}.$
Therefore, $u_{i}$ starts to increase again. We conclude that _invariant
region_ for $u_{i}$, $i=2,3,\cdots,8$ is $[0.4,0.7]$. For $u_{1}$ and $u_{9}$,
we claim that their values cannot fall below $0$, in fact, from the OFF mode,
when $u_{1}$ and $u_{9}$ go down to 0, we have

$\frac{du_{1}}{dt}=-2u_{1}+u_{2}+9=u_{2}+9>0,\qquad\frac{du_{9}}{dt}=u_{8}-2u_{9}+1=u_{8}+1>0,$

which means the values of $u_{1}$ and $u_{9}$ will start to go up again which
prevents the values fall further into negatives. Hence, the _invariant region_
for $u_{1}$ and $u_{9}$ is $[0,0.7]$.

#### Traffic Flow Model.

We consider the model appearing in [26]. The switched PDE problem is a LWR PDE
[24] with the triangular flux function. The flux function and two PDE modes
are:

$\phi(u)=\begin{cases}v_{1}u,&~{}x<u_{c},\\\ v_{2}(\omega-u),&~{}x\geq
u_{c}.\end{cases}~{}~{}\text{mode}=\begin{cases}u_{t}+v_{1}u_{x}=0,~{}x<u_{c},\\\
u_{t}-v_{2}u_{x}=0,~{}x\geq u_{c}.\end{cases}$ (11)

We chose $v_{1}=3$, $v_{2}=1$, $\omega=4$ and $u_{c}=1$. The forward traffic
flow maintains a speed equal to $3$ and the backward wave maintains a speed
equal to $1$. Moreover, $u_{c}$ equals $1$ which is the guard condition for
switching. Lastly, $\omega$ is the parameter specified in backward wave. The
diagram of the model is in Figure 11.

Figure 11: PDHA diagram for the traffic model analyzed. The left circle
indicates the free flow mode and the right circle indicates the congestion
mode. The guard conditions are specified as greater equal than $1$ or less
than $1$. The initial condition is $\Psi(x)$.

Initially, the regions,
$\\{0,...,0.9\\}\cup\\{1.3,...,3.4\\}\cup\\{3.8,...,10.0\\}$, are assigned a
value $0$ for free flow mode. The other remaining areas,
$\\{1.0,1,1,1.2\\}\cup\\{3.5,3.6,3.7\\}$, are assigned a value $1$ for
congestion mode. The Equation 11 shows the free flow mode carries the traffic
forward and congestion pushes the traffic backwards. Once the forward and
backward waves meet each other, the forward wave merges into the backward wave
and starts to move back. The traffic leaves the system and no longer enters
again when it reaches the boundary. For simplicity, no incoming traffic is
considered.

We can facilitate simulation if we harness the theoretical aspects of linear
hyperbolic equations. To simulate the first-order wave equation, only a one-
side scheme is feasible and the low accuracy of the scheme requires a very
dense discretization [46] which makes the computation task a nightmare. Thus,
the simulation is just done by moving the waves along the axis. The results
are shown in Figure 12(a) and 12(b).

(a) $t=1$.

(b) $t=3$

Figure 12: The left subfigure shows the simulation results of the traffic
model at $t=1$. A backward wave appears at the boundary $x=0$. A forward wave
starting at $[3.9,4.0]$ has propagated to the region $[6,9,7.0]$. The right
subfigure shows the simulation results of the traffic model at $t=3$. Only one
backward wave remains.

At $t=1$, the backward wave appearing at the boundary $x=0$ is about to leave.
Wave originating from $[3.5,3.7]$ moves to the place around $2.4$. The forward
wave starting at $[3.9,4.0]$ propagates to the region $[6,9,7.0]$. The
_discrete partition_ $p_{d}$ changes to $0$ for points
$\\{0.3,0.4,...,2.3,2.4\\}\cup\\{2.8,2.9,...,9.9,10\\}$ and $1$ for points
$\\{0,0.1,0.2\\}\cup\\{2.5,2.6,2.7\\}$. At $t=3$, only one single backward
wave remains. $p_{d}=0$ for $\\{0,0.1,...,0.7,0.8\\}\cup[1.1,1.2,...,9.9,10]$
and $p_{d}=1$ for $\\{0.9,1.0\\}$. Here we use the explicit solutions instead
of numerical solutions for the ODE system due to the transport feature of the
traffic model. Simulations show that the traffic merges around $t=0.5$ and
eventually all flows leave the system. Around the merging location, the area
that used to be in the free mode switches to the congestion mode.

##  6 Conclusion

In this paper, we propose a theoretical model called PDHA for modelling PDE
dynamic systems. PDHA involves novel features such as the notion of domain
$X$, which is used to define the spatial location, and domain partition $P$,
which is used to describe the mode occupation and domain changing with respect
to time. After building the theory for PDHA, we present another model called
discrete space PDHA that we construct for the purpose of analysis. In discrete
space PDHA, the discretization relation and scheme are proposed to formalize
the discrete model. Additionally, the partition and space mode are replaced by
a discrete partition, making the analysis easier. Moreover, we formally
defined concepts such as time trajectory, model execution, Zeno behavior,
reachability analysis, and determinism for DSPDHA. The paper also displays
explorations towards the relations of the three models.

Although a few results and similarities are presented regarding DSPDHA and HA,
other topics such as invariants, uniqueness, and continuity remain unexplored.
The dynamic properties we proposed are only for DSPDHA, there is no similar
conclusion for the continuous PDHA. Also, in our examples, we simply consider
a one-dimension uniform discretization using easy FDMs. Other approaches like
generalized finite difference and finite element methods can also play a
critical role if an irregular domain is considered. Deciding DSPDHA from PDHA
is also a challenging endeavor. Thus, an approach for measuring the distance
between the approximated DSPDHA and real PDHA is deeply needed.

It is worth mentioning that the number of ODEs in the finite difference scheme
(FDM) framework depends on the chosen partition. To obtain accurate and
highly-resolved solutions, a fine partition becomes indispensable, which
consequently leads to high-dimensional ODE systems. In such cases, the use of
deep neural network models [48] could potentially offer valuable insights and
broaden the applications of our approach. Exploring the potential of deep
neural networks in this context is an avenue we plan to investigate in future
research.

##  7 Acknowledgements

W. Xiang was supported by the National Science Foundation, under NSF CAREER
Award no. 2143351, and NSF CNS Award no. 2223035.

## References

  * [1] E. A. Lee, Cyber physical systems: Design challenges, in: 2008 11th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing (ISORC), IEEE, 2008, pp. 363–369.
  * [2] S. N. Krishna, A. Trivedi, Hybrid automata for formal modeling and verification of cyber-physical systems, arXiv preprint arXiv:1503.04928.
  * [3] H.-D. Tran, W. Xiang, T. T. Johnson, S. Bak, Reachability analysis for one dimensional linear parabolic equations, 6th IFAC Conference on Analysis and Design of Hybrid Systems.
  * [4] W. Xiang, On equivalence of two stability criteria for continuous-time switched systems with dwell time constraint, Automatica 54 (2015) 36–40.
  * [5] W. Xiang, Necessary and sufficient condition for stability of switched uncertain linear systems under dwell-time constraint, IEEE Transactions on Automatic Control 61 (11) (2016) 3619–3624.
  * [6] W. Xiang, Parameter-memorized lyapunov functions for discrete-time systems with time-varying parametric uncertainties, Automatica 87 (2018) 450–454.
  * [7] W. Xiang, J. Lam, J. Shen, Stability analysis and l1-gain characterization for switched positive systems under dwell-time constraint, Automatica 85 (2017) 1–8.
  * [8] W. Xiang, H.-D. Tran, T. T. Johnson, Robust exponential stability and disturbance attenuation for discrete-time switched systems under arbitrary switching, IEEE Transactions on Automatic Control 63 (5) (2017) 1450–1456.
  * [9] L. Zhang, W. Xiang, Mode-identifying time estimation and switching-delay tolerant control for switched systems: An elementary time unit approach, Automatica 64 (2016) 174–181.
  * [10] Z. Xu, H. Su, P. Shi, R. Lu, Z.-G. Wu, Reachable set estimation for markovian jump neural networks with time-varying delays, IEEE transactions on cybernetics 47 (10) (2016) 3208–3217.
  * [11] W. Xiang, H.-D. Tran, T. T. Johnson, Output reachable set estimation for switched linear systems and its application in safety verification, IEEE Transactions on Automatic Control 62 (10) (2017) 5380–5387.
  * [12] W. Xiang, H.-D. Tran, T. T. Johnson, On reachable set estimation for discrete-time switched linear systems under arbitrary switching, in: 2017 American Control Conference (ACC), IEEE, 2017, pp. 4534–4539.
  * [13] M. Johansson, A. Rantzer, Computation of piecewise quadratic lyapunov functions for hybrid systems, in: 1997 European Control Conference (ECC), IEEE, 1997, pp. 2005–2010.
  * [14] M. Margaliot, G. Langholz, Necessary and sufficient conditions for absolute stability: the case of second-order systems, IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications 50 (2) (2003) 227–234.
  * [15] S. Pettersson, B. Lennartson, Stabilization of hybrid systems using a min-projection strategy, in: Proceedings of the 2001 American Control Conference.(Cat. No. 01CH37148), Vol. 1, IEEE, 2001, pp. 223–228.
  * [16] A. S. Morse, Supervisory control of families of linear set-point controllers-part i. exact matching, IEEE transactions on Automatic Control 41 (10) (1996) 1413–1431.
  * [17] L. I. Allerhand, U. Shaked, Robust stability and stabilization of linear switched systems with dwell time, IEEE Transactions on Automatic Control 56 (2) (2010) 381–386.
  * [18] J. P. Hespanha, A. S. Morse, Stability of switched systems with average dwell-time, in: Proceedings of the 38th IEEE conference on decision and control (Cat. No. 99CH36304), Vol. 3, IEEE, 1999, pp. 2655–2660.
  * [19] L. Zhang, H. Gao, Asynchronously switched control of switched linear systems with average dwell time, Automatica 46 (5) (2010) 953–958.
  * [20] L. C. Evans, Partial differential equations, American Mathematical Society.
  * [21] T. Bao, X. Jia, J. Zwart, J. Sadler, A. Appling, S. Oliver, T. T. Johnson, Partial differential equation driven dynamic graph networks for predicting stream water temperature, in: 2021 IEEE International Conference on Data Mining (ICDM), IEEE, 2021, pp. 11–20.
  * [22] T. Bao, S. Chen, T. T. Johnson, P. Givi, S. Sammak, X. Jia, Physics guided neural networks for spatio-temporal super-resolution of turbulent flows, in: Uncertainty in Artificial Intelligence, PMLR, 2022, pp. 118–128.
  * [23] A. M. Bayen, R. L. Raffard, C. J. Tomlin, Network congestion alleviation using adjoint hybrid control: Application to highways, in: International Workshop on Hybrid Systems: Computation and Control, Springer, 2004, pp. 95–110.
  * [24] M. J. Lighthill, G. B. Whitham, On kinematic waves ii. a theory of traffic flow on long crowded roads, Proc. R. Soc. Lond. A 229 (1178) (1955) 317–345.
  * [25] L. Muñoz, X. Sun, R. Horowitz, L. Alvarez, Traffic density estimation with the cell transmission model, in: American Control Conference, 2003. Proceedings of the 2003, Vol. 5, IEEE, 2003, pp. 3750–3755.
  * [26] C. G. Claudel, A. M. Bayen, Solutions to switched Hamilton–Jacobi equations and conservation laws using hybrid components, in: International Workshop on Hybrid Systems: Computation and Control, Springer, 2008, pp. 101–115.
  * [27] T. A. Henzinger, The theory of hybrid automata, in: Proceedings 11th Annual IEEE Symposium on Logic in Computer Science, IEEE, 1996, pp. 278–292.
  * [28] R. Alur, C. Courcoubetis, T. A. Henzinger, P.-H. Ho, Hybrid automata: An algorithmic approach to the specification and verification of hybrid systems, in: International Hybrid Systems Workshop, Springer, 1991, pp. 209–229.
  * [29] T. Bao, et al., Modelling physics-based dynamic system using machine learning, Ph.D. thesis, Vanderbilt University (2023).
  * [30] D. G. Mallet, L. G. De Pillis, A cellular automata model of tumor–immune system interactions, Journal of theoretical biology 239 (3) (2006) 334–350.
  * [31] A. Banerjee, S. K. Gupta, Spatio-temporal hybrid automata for safe cyber-physical systems: A medical case study, in: Proceedings of the ACM/IEEE 4th International Conference on Cyber-Physical Systems, 2013, pp. 71–80.
  * [32] C. Tomlin, J. Lygeros, S. Sastry, Computing controllers for nonlinear hybrid systems, in: Hybrid Systems: Computation and Control: Second International Workshop, HSCC’99 Berg en Dal, The Netherlands, March 29–31, 1999 Proceedings 2, Springer, 1999, pp. 238–255.
  * [33] R. Bonnerot, P. Jamet, Numerical computation of the free boundary for the two-dimensional stefan problem by space-time finite elements, Journal of Computational Physics 25 (2) (1977) 163–181.
  * [34] J. M. Aitchison, S. Howison, Computation of hele-shaw flows with free boundaries, Journal of Computational Physics 60 (3) (1985) 376–390.
  * [35] A. Friedman, V. Principles, Free boundary problems, Malabar, Fla.: RE Krieger 258\.
  * [36] L. A. Caffarelli, S. Salsa, S. Salsa, A geometric approach to free boundary problems, Vol. 68, American Mathematical Soc., 2005.
  * [37] A. Friedman, Free boundary problems in science and technology, Notices of the AMS 47 (8) (2000) 854–861.
  * [38] G. Ryskin, L. Leal, Numerical solution of free-boundary problems in fluid mechanics. part 1. the finite-difference technique, Journal of fluid mechanics 148 (1984) 1–17.
  * [39] G. Ryskin, L. Leal, Numerical solution of free-boundary problems in fluid mechanics. part 2. buoyancy-driven motion of a gas bubble through a quiescent liquid, Journal of Fluid Mechanics 148 (1984) 19–35.
  * [40] F. M. Hante, G. Leugering, T. I. Seidman, Modeling and analysis of modal switching in networked transport systems, Applied Mathematics and Optimization 59 (2) (2009) 275–292.
  * [41] C. J. Tomlin, J. Lygeros, S. S. Sastry, A game theoretic approach to controller design for hybrid systems, Proceedings of the IEEE 88 (7) (2000) 949–970.
  * [42] I. S. Strub, A. M. Bayen, Weak formulation of boundary conditions for scalar conservation laws: An application to highway traffic modelling, International Journal of Robust and Nonlinear Control: IFAC-Affiliated Journal 16 (16) (2006) 733–748.
  * [43] P. R. Halmos, Naive set theory, Courier Dover Publications, 2017.
  * [44] G. D. Smith, Numerical solution of partial differential equations: finite difference methods, Oxford university press, 1985.
  * [45] J. Lygeros, K. H. Johansson, S. N. Simic, J. Zhang, S. S. Sastry, Dynamical properties of hybrid automata, IEEE Transactions on automatic control 48 (1) (2003) 2–17.
  * [46] J. W. Thomas, Numerical partial differential equations: finite difference methods, Vol. 22, Springer Science & Business Media, 2013.
  * [47] J. Rauch, M. Reed, Jump discontinuities of semilinear, strictly hyperbolic systems in two variables: Creation and propagation, Communications in Mathematical Physics 81 (2) (1981) 203–227.
  * [48] R. T. Chen, Y. Rubanova, J. Bettencourt, D. K. Duvenaud, Neural ordinary differential equations, Advances in neural information processing systems 31.


# UM6P-CS at SemEval-2022 Task 11: Enhancing Multilingual and Code-Mixed
Complex Named Entity Recognition via Pseudo Labels using Multilingual
Transformer

Abdellah El Mekki1 Abdelkader El Mahdaouy1 Mohammed Akallouch${}^{1},^{2}$
Ismail Berrada1 Ahmed Khoumsi 3
1School of Computer Sciences, Mohammed VI Polytechnic University, Morocco
2Faculty of Sciences Dhar EL Mahraz, Sidi Mohamed Ben Abdellah University,
Morocco
3Dept. Electrical & Computer Engineering, University of Sherbrooke, Canada
<EMAIL_ADDRESS>
###### Abstract

Building real-world complex Named Entity Recognition (NER) systems is a
challenging task. This is due to the complexity and ambiguity of named
entities that appear in various contexts such as short input sentences,
emerging entities, and complex entities. Besides, real-world queries are
mostly malformed, as they can be code-mixed or multilingual, among other
scenarios. In this paper, we introduce our submitted system to the
Multilingual Complex Named Entity Recognition (MultiCoNER) shared task. We
approach the complex NER for multilingual and code-mixed queries, by relying
on the contextualized representation provided by the multilingual Transformer
XLM-RoBERTa. In addition to the CRF-based token classification layer, we
incorporate a span classification loss to recognize named entities spans.
Furthermore, we use a self-training mechanism to generate weakly-annotated
data from a large unlabeled dataset. Our proposed system is ranked 6th and 8th
in the multilingual and code-mixed MultiCoNER’s tracks respectively.

##  1 Introduction

Recent named entity recognition (NER) models have achieved great performance
for many languages and using various benchmark datasets such as CoNLL2003 and
OntoNotes 5.0 Devlin et al. (2019). However, it is unclear whether or not
these systems can handle ambiguous and complex entities, especially in the
case of short and low-context settings Augenstein et al. (2017). It is also
unclear weather these systems can be deployed in real-world scenarios where
the input data can be in different languages or code-mixed Luken et al.
(2018); Hanselowski et al. (2018). In fact, to illustrate these issues, if
consider the example of complex named entities such as the titles of creative
works (movies, songs, books …), they are hard to be recognized by simple NER
systems. This is due to their syntactic ambiguity and the form they can take
from one context to another. For instance, they can be as an imperative clause
("Dial M for Murder") or a proposition ("On the beach") which refers to the
name of a movie. Thus, it is important to check the performance of NER systems
in these scenarios.

The complexity of named entities can be due to three main reasons:

  1. 1.

Complex entities: These entities can be represented as complex infinitives (To
Kill a Mockingbird) or full clauses (Mr.Smith Goes to Washington).
Additionally, they can be represented as noun phrases or gerunds. State-of-
the-art systems Aguilar et al. (2017) have shown that it is hard to recognize
such entities.

  2. 2.

Ambiguous entities and contexts: These types of entities are context-dependent
as they can refer to named entities in some contexts, but not in others.
“Among Us” which refers to the name of a video game is an example of this
challenge. This situation is even more challenging Mayhew et al. (2019) in the
case of short sentences with minimal context such as questions or search
queries, which most of the time lack some features such as capitalization or
punctuation.

  3. 3.

Emerging entities: This challenge mimics the real-world scenario with many
unseen entities, as new named entities are always appearing due to the release
of new books, songs, or movies within a short period of time.

It is well known that the state-of-the-art performance reached by current NER
systems is mainly due to the presence of easy entities and well-formed input
texts Augenstein et al. (2017). Nevertheless, they yield weak performance when
applied in multilingual/code-switched input texts having complex or unseen
entities. It is also worth mentioning that the reached state-of-the-art
results by current NER systems have been achieved using Transformers-based
pre-trained language models Devlin et al. (2019) that are known to encode the
context of input texts and tokens.

In this paper, we introduce our participating system to the MultiCoNER shared
task Malmasi et al. (2022b), in particular, the complex MultiCoNER tracks of
multilingual and code-switched queries. Our system relies on a deep learning
model based on the multilingual Transformer-based pre-trained language model
XLM-RoBERTa Conneau et al. (2020). To handle the complexity of the two tracks,
our model is trained using two optimization objectives, as well as for self-
training. The main components of our system can be summarized as follow:

  * •

Optimization of entities span loss: We train our model to recognize entities
spans as an auxiliary task. The aim is to help the model detect the full
entities expressions in an input sentence.

  * •

Incorporation of Conditional Random Field (CRF) Lafferty et al. (2001) layer:
We incorporate a CRF layer on top of the Transformer representations to fully
exploit the mutual information between tokens in an input sentence.

  * •

Self-training on unlabeled data: we create a weakly-supervised data based on
the model predictions on unlabeled data.

The rest of this paper is organized as follows. Section 2 presents the related
work. Section 3 describes the dataset and the sub-tasks of SemEval-2022 Task
11 Malmasi et al. (2022b). In section 4, we present our system overview.
Section 5 summarizes and discusses the obtained results for both multilingual
and code-mixed tracks. Finally, Section 5 concludes the paper.

##  2 Related Work

During the last years, neural network-based approaches have contributed to
improving the performance of NER systems Panchendrarajan and Amaresan (2018);
Devlin et al. (2019). This was mainly achieved thanks to word embeddings.
Static word embeddings are fed to BiLSTM-CRF models and have helped eliminate
manual feature engineering while achieving better performance. On the other
hand, Transformer-based Language Models Devlin et al. (2019); Conneau et al.
(2020) have greatly improved the NER results thanks to their contextualized
word representations.

However, these models may fail when recognizing new or complex entities Luken
et al. (2018); Hanselowski et al. (2018). These challenges are reflecting the
real-world setting. Recently, Meng et al. (2021) have proposed an approach to
tackle these challenges by using a contextual Gazetteer Representation encoder
which can be fused with word-level models. The results have shown that this
method enhances the F1-score by +49% in the uncased setting. This work has
been mainly applied to the English language. Finally, in another work, Fetahu
et al. (2021) have explored the code-mixed NER scenario using multilingual
Transformers. They have combined the Mixture-of-Experts model with existing
multilingual Transformers models to incorporate the multi-lingual gazetteers.
The experiments have demonstrated that their proposed approach enhances the
F1-score by +31% in the Code-Mixed NER over the baseline model.

##  3 Data

The dataset of the MultiCoNER (Multilingual Complex Named Entity Recognition)
shared task Malmasi et al. (2022a) is provided to tackle thirteen different
tracks, eleven tracks cover the monolingual cases, while the remaining two
tracks cover code-mixed and multilingual data. In this paper, we focus on the
last two tracks.

The multilingual track covers eleven languages (English, Spanish, Dutch,
Russian, Turkish, Korean, Farsi, German, Chinese, Hindi, and Bangla), while
the code-mixed track covers a subset of these languages. In both tracks, the
entities are annotated into six types: PER, LOC, GRP, CORP, PROD, and CW.
Table 1 presents the size of the train and test datasets provided for these
tracks. We notice that the multilingual track has more data than the code-
mixed track, and the test datasets are larger than the train datasets for both
tracks.

| Multilingual | Code-mixed
---|---|---
Train | 168300 | 1500
Test | 471911 | 100000
Table 1: The size of the train and the test datasets for the multilingual and
code-mixed tracks.

The provided datasets are labeled using the IOB format which is used for
sequence labeling tasks. Table 2 presents the distribution of the entities and
the spans in the train datasets for both tracks.

|  | Classification tasks
---|---|---
|  | Named entity | Entity Span
| Class | LOC | PER | PROD | GRP | CORP | CW | Entity Span |  Not Entity Span
Mutilingual | % | 22.02 | 18.76 | 15.0 | 14.0 | 14.11 | 16.12 | 38.82 |  61.17
Code-Mixed | % | 18.27 | 16.63 | 17.88 | 13.9 | 16.63 | 16.69 | 41.71 |  58.28

Table 2: The distribution of named entities and entities spans in the train
dataset for the multilingual and code-mixed tracks

##  4 Methodology

Before discussing the methodology of our proposed system, we assume that we
have $n$ labeled sentences with named-entities
$D=\\{(x_{i}^{t},y_{i}^{t})\\}_{1}^{n}$ and $m$ unlabeled sentences
$U=\\{(x_{i}^{u})\\}_{1}^{m}$, where $x_{i}=\\{x_{i,1},x_{i,2},...,x_{i,l}\\}$
represents a sentence containing $l$ tokens, while
$y_{i}=\\{y_{i,1},y_{i,2},...,y_{i,l}\\}$ are the $l$ labels corresponding to
these $l$ tokens.

The proposed system incorporates 4 components used on top of the pre-trained
Transformer encoder. In the following, we describe each component of our
system.

###  4.1 Multilingual Transformer encoder

To encode each word in the input sentence, we use the XLM-RoBERTa (XLM-R)
(Conneau et al., 2020). It is a multilingual pre-trained transformer encoder
network. We choose to use this encoder for the following reasons: 1) XLM-R is
the state-of-the-art encoder in the multilingual and code-mixed settings, and
2) It has been trained on 100 languages including the languages covered in the
multilingual and code-mixed tracks. This ensures a good contextualized
representation for the input sentences despite their language.

This model was mainly trained using the Mask Language Modeling Devlin et al.
(2019). For an input sentence, 15% of the words are randomly masked, then the
model tries to predict the masked words. As a result of this training process,
the model learns the representations of dimension $d$ for the input words of
100 languages that can be fine-tunned on a downstream tasks such as sequence
classification or sequence labeling.

###  4.2 Span classification module

Span classification is a span-wise classifier, where the aim is to classify
whether or not, a sequence of tokens are representing a named entity span
based on their semantics. It is a binary classification task as the model
predicts 1 if the span is a named entity while it predicts 0 if not.

Given $H=[h_{1},h_{2},...,h_{k}]$, the vector representations of the $k$ sub-
tokens contained in a span $S$, to learn a representation that encodes all the
span tokens, we follow the same approach used in Essefar et al. (2021); El
Mekki et al. (2021b); El Mahdaouy et al. (2021), where an attention layer
Bahdanau et al. (2015) learns the span representations $SH$ based on its
tokens, as follows:

$C=tanh(HW^{a})$ $\alpha=softmax(C^{T}W^{\alpha})$ $SH=\alpha\cdot H^{T}$

where $W^{a}\in\mathbb{R}^{d\times 1}$, $W^{\alpha}\in\mathbb{R}^{k\times k}$
are the trainable parameters of the attention layer, $C\in\mathbb{R}^{k\times
1}$ and $\alpha\in[0,1]^{k}$ weights the word representations according to
their importance for the task at hand.

The vector representations $SH$ of all the spans in an input sentence are then
fed to a feed-forward neural network which classifies whether or not, the
input representation refers to a named-entity span.

As illustrated in table 2, we notice that the majority of spans do not
represent a named entity. To tackle this imbalanced data issue, we follow Li
et al. (2020) in using the Focal Loss (FL) (Lin et al., 2017). The FL is given
by:

$FL(y,\hat{p})=-\alpha_{y}\left(1-\hat{p}_{y}\right)^{\gamma}\log(\hat{p}_{y})$
(1)

where, $y\in\\{0,1\\}$ denotes the span’s label,
$\hat{p}=(\hat{p}_{0},\hat{p}_{1})$ is a vector representing the predicted
probability distribution over the labels, $\alpha_{y}$ is the weight of label
$y$, and $\gamma$ controls the contribution of high-confidence predictions in
the loss. The performed experiments showed that $\gamma=0.5$ gives the best
result.

As the provided dataset in this shared task has been annotated based on named
entities, we adjust it for the span classification task. Therefore, we label
all the named entities spans as 1 while the rest of spans has been labeled as
0.

###  4.3 NER classification using CRF-Layer

Most NER systems using Transformers rely on using the first sub-token of each
word as input to the classification layer Devlin et al. (2019). In our system,
we follow the work of Ács et al. (2021) in using a pooling of the sub-tokens
of each word in the input sentence.

Given $H=[h_{1},h_{2},...,h_{p}]$, the vector representations of the all the
sub-tokens contained in a word $w$, an attention layer learns the word pooled
representations based on its sub-tokens following the same method explained in
section 4.2.

The pooled representations are then fed to the classification layer which is a
Conditional Random Field (CRF) layer in our system. We opt for CRF mainly
because the Softmax layer does not take into consideration the dependencies
between tokens. The self-attention mechanism, performed by the Transformer
encoder, encodes these dependencies in the output vectors of the input
sentence. While the CRF which is common in sequence labeling tasks ensures
output consistency, it transforms the sequence of input word representations
to a sequence of probability distributions, therefore, each label prediction
depends on the other predictions in the same input sentence.

###  4.4 Self-training

To take profit from the provided unlabeled dataset in this shared task, we
generate a weakly-annotated dataset and re-train the developed model on it.
This method has been applied differently in several works Khalifa et al.
(2021); El Mekki et al. (2021a); Huang et al. (2021). In our work, we apply
the following pipeline:

  1. 1.

We train a model $M$ (based on span classification and NER-CRF explained in
the previous subsections) using the provided labeled data $D$.

  2. 2.

We use the trained model $M$ to predict the labels of the provided unlabeled
data. Then we build a weakly-annotated data $U$

  3. 3.

We concatenate the datasets $T$ and $U$ and re-train the sequence labeling
model.

It is worth mentioning that during the self-training phase, we remove the span
classification module.

##  5 Experiments and results

###  5.1 Experimental setup

We use the PyTorch framework and the Transformers libraries for the
implementation of our proposed system. The training of the model is performed
on a server with a single Nvidia Tesla P100 with 16GB of RAM. XLM-RoBERTa
Large is used as our multilingual Transformer encoder. Adam optimizer with a
learning rate of $1e-5$ is used for all experiments. The system is trained
with a batch size of 16 and for 20 epochs.

For the multilingual track, we train our model on the provided labeled
multilingual data, then we use the best epoch’s model to leverage pseudo-
labels from the unlabeled test data, and we re-train the model again from
scratch. Besides, for the code-mixed track, we combine the provided data with
the training data of the multilingual track and we follow the same training
pipeline of the multilingual track.

###  5.2 Results

|  | Multilingual track | Code-mixed track
---|---|---|---
|  | Precision | Recall | F1 | Precision | Recall | F1
Baseline |  | - | - | 54.10 | - | - | 58.10
BERT-CRF |  | 68.59 | 69.30 | 68.00 | 78.47 | 78.92 | 78.78
| \+ Span Classification | 70.71 | 70.56 | 70.25 | 78.30 | 78.77 | 78.52
| \+ Self-training | 73.21 | 72.51 | 72.49 | 79.38 | 79.08 | 79.21
Table 3: Official Complex NER F1-scores on the multilingual and code-mixed tracks using the proposed system. | Multilingual track | Code-mixed track
---|---|---
| Precision | Recall | F1 | Precision | Recall | F1
LOC | 72.24 | 81.41 | 76.01 | 80.37 | 83.04 | 81.68
PER | 85.20 | 81.40 | 83.13 | 88.02 | 88.67 | 88.35
PROD | 70.54 | 70.24 | 70.00 | 82.68 | 80.51 | 81.58
GRP | 69.78 | 63.6 | 66.26 | 70.85 | 73.02 | 71.92
CW | 67.58 | 68.74 | 67.95 | 75.00 | 74.27 | 74.63
CORP | 73.91 | 69.68 | 71.60 | 79.36 | 74.99 | 77.11
Table 4: Official Complex NER F1-scores per entity on the multilingual and
code-mixed tracks using the proposed system.

Table 3 presents the submitted results for the multilingual and code-mixed
tracks using our system. The first row in the table presents the baseline
results on the test set published by the shared task organizers. The
performance achieved by our best submission largely outperforms the baseline
results in both tracks. In fact, the performance using our model boosts the
baseline score by 18.39 and 21.11 F1-score points in the multilingual track
and the code-mixed track, respectively. The table also reports the performance
of our system during the three stages (ablation study):

  * •

The BERT-CRF model that incorporates the named-entity recognition
classification layer with CRF,

  * •

The span classification objective, and

  * •

The self-training.

The results show that the span classification stage enhances the performance
of both tracks: the F1-scores achieved using the span classification are
70.25% for multilingual track and 78.52 % for the code-mixed track. However,
we notice that the span classification has significantly boosted the F1-score
compared to the BERT-CRF model for the multilingual track, while there is a
small performance loss in the case of the code-mixed track. When performing
self-training on the predictions extracted from the model using the span
classification stage, a large gain has been achieved in both tracks. For the
multilingual track, the F1-score obtained using self-training is 72.49% with a
gain of 3.18% compared to the system without self-training. For the code-mixed
track, our system has achieved the F1-score of 79.21% with a gain of 0.87%
compared to the system without self-training.

Finally, Table 4 presents the performance of our best submission for the
multilingual and code-mixed tracks. The proposed system fails the most in
predicting the GRP entities for both tracks, meanwhile, it gives its best
performance when predicting the PER entities.

##  6 Conclusion

In this paper, we present our Named Entity Recognition (NER) system for
complex scenarios on multilingual and code-mixed queries. Our system relies on
4 components: a multilingual transformer encoder, an entity span
classification module, a CRF-layer, and a self-training mechanism that
leverages information from unlabeled data. We use our system to submit our
predictions in the SemEval-2022 Task 11 within the multilingual and code-mixed
tracks. The results show that the use of multilingual Transformer and self-
training enhances the results in both multilingual and code-mixed cases.
Moreover, the incorporation of the span classification module and the CRF
layer allow better recognition of complex named entities.

## References

  * Ács et al. (2021) Judit Ács, Ákos Kádár, and Andras Kornai. 2021.  Subword pooling makes a difference.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 2284–2295, Online. Association for Computational Linguistics.
  * Aguilar et al. (2017) Gustavo Aguilar, Suraj Maharjan, Adrian Pastor López-Monroy, and Thamar Solorio. 2017.  A multi-task approach for named entity recognition in social media data.  In _Proceedings of the 3rd Workshop on Noisy User-generated Text_ , pages 148–153, Copenhagen, Denmark. Association for Computational Linguistics.
  * Augenstein et al. (2017) Isabelle Augenstein, Leon Derczynski, and Kalina Bontcheva. 2017.  Generalisation in named entity recognition: A quantitative analysis.  _Computer Speech & Language_, 44:61–83.
  * Bahdanau et al. (2015) Dzmitry Bahdanau, Kyunghyun Cho, and Yoshua Bengio. 2015.  Neural machine translation by jointly learning to align and translate.  In _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_.
  * Conneau et al. (2020) Alexis Conneau, Kartikay Khandelwal, Naman Goyal, Vishrav Chaudhary, Guillaume Wenzek, Francisco Guzmán, Edouard Grave, Myle Ott, Luke Zettlemoyer, and Veselin Stoyanov. 2020.  Unsupervised cross-lingual representation learning at scale.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 8440–8451, Online. Association for Computational Linguistics.
  * Devlin et al. (2019) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2019.  BERT: Pre-training of deep bidirectional transformers for language understanding.  In _Proceedings of the 2019 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume 1 (Long and Short Papers)_ , pages 4171–4186, Minneapolis, Minnesota. Association for Computational Linguistics.
  * El Mahdaouy et al. (2021) Abdelkader El Mahdaouy, Abdellah El Mekki, Kabil Essefar, Nabil El Mamoun, Ismail Berrada, and Ahmed Khoumsi. 2021.  Deep multi-task model for sarcasm detection and sentiment analysis in Arabic language.  In _Proceedings of the Sixth Arabic Natural Language Processing Workshop_ , pages 334–339, Kyiv, Ukraine (Virtual). Association for Computational Linguistics.
  * El Mekki et al. (2021a) Abdellah El Mekki, Abdelkader El Mahdaouy, Ismail Berrada, and Ahmed Khoumsi. 2021a.  Domain adaptation for Arabic cross-domain and cross-dialect sentiment analysis from contextualized word embedding.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 2824–2837, Online. Association for Computational Linguistics.
  * El Mekki et al. (2021b) Abdellah El Mekki, Abdelkader El Mahdaouy, Kabil Essefar, Nabil El Mamoun, Ismail Berrada, and Ahmed Khoumsi. 2021b.  BERT-based multi-task model for country and province level MSA and dialectal Arabic identification.  In _Proceedings of the Sixth Arabic Natural Language Processing Workshop_ , pages 271–275, Kyiv, Ukraine (Virtual). Association for Computational Linguistics.
  * Essefar et al. (2021) Kabil Essefar, Abdellah El Mekki, Abdelkader El Mahdaouy, Nabil El Mamoun, and Ismail Berrada. 2021.  CS-UM6P at SemEval-2021 task 7: Deep multi-task learning model for detecting and rating humor and offense.  In _Proceedings of the 15th International Workshop on Semantic Evaluation (SemEval-2021)_ , pages 1135–1140, Online. Association for Computational Linguistics.
  * Fetahu et al. (2021) Besnik Fetahu, Anjie Fang, Oleg Rokhlenko, and Shervin Malmasi. 2021.  Gazetteer Enhanced Named Entity Recognition for Code-Mixed Web Queries.  In _Proceedings of the 44th International ACM SIGIR Conference on Research and Development in Information Retrieval_ , pages 1677–1681.
  * Hanselowski et al. (2018) Andreas Hanselowski, Hao Zhang, Zile Li, Daniil Sorokin, Benjamin Schiller, Claudia Schulz, and Iryna Gurevych. 2018.  UKP-athene: Multi-sentence textual entailment for claim verification.  In _Proceedings of the First Workshop on Fact Extraction and VERification (FEVER)_ , pages 103–108, Brussels, Belgium. Association for Computational Linguistics.
  * Huang et al. (2021) Kaiyu Huang, Junpeng Liu, Degen Huang, Deyi Xiong, Zhuang Liu, and Jinsong Su. 2021\.  Enhancing Chinese word segmentation via pseudo labels for practicability.  In _Findings of the Association for Computational Linguistics: ACL-IJCNLP 2021_ , pages 4369–4381, Online. Association for Computational Linguistics.
  * Khalifa et al. (2021) Muhammad Khalifa, Muhammad Abdul-Mageed, and Khaled Shaalan. 2021.  Self-training pre-trained language models for zero- and few-shot multi-dialectal Arabic sequence labeling.  In _Proceedings of the 16th Conference of the European Chapter of the Association for Computational Linguistics: Main Volume_ , pages 769–782, Online. Association for Computational Linguistics.
  * Lafferty et al. (2001) John D. Lafferty, Andrew McCallum, and Fernando C. N. Pereira. 2001.  Conditional random fields: Probabilistic models for segmenting and labeling sequence data.  In _Proceedings of the Eighteenth International Conference on Machine Learning_ , ICML ’01, page 282–289, San Francisco, CA, USA. Morgan Kaufmann Publishers Inc.
  * Li et al. (2020) Xiaoya Li, Xiaofei Sun, Yuxian Meng, Junjun Liang, Fei Wu, and Jiwei Li. 2020.  Dice loss for data-imbalanced NLP tasks.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 465–476, Online. Association for Computational Linguistics.
  * Lin et al. (2017) T. Lin, P. Goyal, R. Girshick, K. He, and P. Dollar. 2017.  Focal loss for dense object detection.  In _2017 IEEE International Conference on Computer Vision (ICCV)_ , pages 2999–3007, Los Alamitos, CA, USA. IEEE Computer Society.
  * Luken et al. (2018) Jackson Luken, Nanjiang Jiang, and Marie-Catherine de Marneffe. 2018.  QED: A fact verification system for the FEVER shared task.  In _Proceedings of the First Workshop on Fact Extraction and VERification (FEVER)_ , pages 156–160, Brussels, Belgium. Association for Computational Linguistics.
  * Malmasi et al. (2022a) Shervin Malmasi, Anjie Fang, Besnik Fetahu, Sudipta Kar, and Oleg Rokhlenko. 2022a.  MultiCoNER: a Large-scale Multilingual dataset for Complex Named Entity Recognition.
  * Malmasi et al. (2022b) Shervin Malmasi, Anjie Fang, Besnik Fetahu, Sudipta Kar, and Oleg Rokhlenko. 2022b.  SemEval-2022 Task 11: Multilingual Complex Named Entity Recognition (MultiCoNER).  In _Proceedings of the 16th International Workshop on Semantic Evaluation (SemEval-2022)_. Association for Computational Linguistics.
  * Mayhew et al. (2019) Stephen Mayhew, Tatiana Tsygankova, and Dan Roth. 2019.  ner and pos when nothing is capitalized.  In _Proceedings of the 2019 Conference on Empirical Methods in Natural Language Processing and the 9th International Joint Conference on Natural Language Processing (EMNLP-IJCNLP)_ , pages 6256–6261, Hong Kong, China. Association for Computational Linguistics.
  * Meng et al. (2021) Tao Meng, Anjie Fang, Oleg Rokhlenko, and Shervin Malmasi. 2021.  GEMNET: Effective gated gazetteer representations for recognizing complex entities in low-context input.  In _Proceedings of the 2021 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies_ , pages 1499–1512.
  * Panchendrarajan and Amaresan (2018) Rrubaa Panchendrarajan and Aravindh Amaresan. 2018.  Bidirectional LSTM-CRF for named entity recognition.  In _Proceedings of the 32nd Pacific Asia Conference on Language, Information and Computation_ , Hong Kong. Association for Computational Linguistics.