# A secure state estimation algorithm
for nonlinear systems under sensor attacks

Michelle S. Chong, Henrik Sandberg, João P. Hespanha M. Chong is with the
Control Systems Technology section at the Department of Mechanical
Engineering, Eindhoven University of Technology<EMAIL_ADDRESS>Sandberg
is with the Division of Decision and Control Systems at KTH Royal Institute of
Techonology<EMAIL_ADDRESS>Hesphana is with the Electrical and Computer
Engineering Department at the University of California Santa Barbara.
<EMAIL_ADDRESS>material is based upon work supported by the U.S.
Office of Naval Research under the MURI grant No. N00014-16-1-2710.

###### Abstract

The state estimation of continuous-time nonlinear systems in which a subset of
sensor outputs can be maliciously controlled through injecting a potentially
unbounded additive signal is considered in this paper. Analogous to our
earlier work for continuous-time linear systems in [1], we term the
convergence of the estimates to the true states in the presence of sensor
attacks as ‘observability under $M$ attacks’, where $M$ refers to the number
of sensors which the attacker has access to. Unlike the linear case, we only
provide a sufficient condition such that a nonlinear system is observable
under $M$ attacks. The condition requires the existence of asymptotic
observers which are robust with respect to the attack signals in an input-to-
state stable sense. We show that an algorithm to choose a compatible state
estimate from the state estimates generated by the bank of observers achieves
asymptotic state reconstruction. We also provide a constructive method for a
class of nonlinear systems to design state observers which have the desirable
robustness property. The relevance of this study is illustrated on monitoring
the safe operation of a power distribution network.

##  I Introduction

The cyber security of dynamical systems have garnered the attention of our
community in the past decade, see [2] and [3] for a tutorial overview. This is
indeed a timely concern as the increasing (cyber) connectivity between
physical systems creates vulnerabilities where malicious cyber attacks can
lead to disastrous consequences.

The focus of this work is on the state estimation of nonlinear dynamical
systems where the sensors have been compromised. This context has been studied
in detail for linear systems in both discrete [4, 5, 6, 7, 8, 9, 10] and
continuous-time [1, 11]. The main thread that underlies achieving state
reconstruction is characterizing the number of sensors which are allowed to be
attacked, and the resulting algorithm is an optimization problem which is
combinatorial in nature. The computational complexity of these algorithms are
addressed in various ways including transforming an $l_{0}$ minimization
problem into a convex one [4], using gradient descent algorithms [5],
employing Satisfiability Modulo Theory (SMT) solvers to reduce search time [6]
and reducing the number candidates [11, 10, 9, 8], to name a few.

Relatively little work has been done for nonlinear systems, where algorithms
were proposed for classes of nonlinear systems in discrete-time [12, 13, 14]
and in continuous-time [15, 16]. Feedback linearizable systems are considered
in [13] and differentially flat systems in [12], which then enables state
estimation using linear techniques. The authors of [14] consider Lur’e systems
and employs the same framework as in [1]. An adaptive observer is designed to
estimate both the states and the attack signals for asymptotically stable
nonlinear systems in [16]. In [15], a uniformly observable nonlinear system is
considered and a high gain observer is designed for each measured output. An
algorithm which exploits redundancy then collects all the state estimates and
provides a state estimate.

In this paper, we consider a continuous-time nonlinear system with $N$ outputs
where each is measured by a potentially compromised sensor. Under the scenario
where $M$ out of the $N$ sensors have been maliciously manipulated, we aim to
reconstruct the states given that we do not know which of the $M$ sensors have
been compromised. If this objective is met, we call such a system observable
under M attacks, a term coined in our earlier work for linear systems [1].

We first provide a sufficient condition in Section IV for observability under
$M$ attacks. The condition calls for the total number of sensors $N$ to be
larger than twice the number of attacked sensors $M$, i.e. $N>2M$. Moreover,
it also requires an observer to be constructed for every combination of $N-2M$
sensor measurements received by the observer, with the crucial property that
the observer is robust towards the attack signals. In other words, each
observer must have an estimation error system which is input-to-state stable
(ISS) [17] with respect to the attack signals. These conditions are consistent
with the key results in the literature for linear systems [4, 1] and a class
of nonlinear systems [15].

This gives rise to an algorithm in Section V, which employs the same framework
proposed in an earlier work for linear systems in [1] by some of the authors
of this paper. The algorithm uses a bank of observers designed to satisfy the
aforementioned properties and picks the state estimate which satisfies a
consistency measure involving a subset of the other state estimates. The
chosen state estimate is shown to converge asymptotically to the true state,
in the presence of sensor attacks, provided that the system is $M$ attack
observable.

In Section VI, we consider a class of nonlinear systems and provide a
systematic method for designing observers which have the desired ISS property
with respect to the attack signal. This work is highly relevant in the remote
monitoring of the local voltage regulation of each customer who is connected
to a power distribution network, which we present in Section VII. All proofs
are provided in the appendix.

##  II Preliminaries

  * •

Let $\mathbb{R}=(-\infty,\infty)$, $\mathbb{R}_{\geq 0}=[0,\infty)$,
$\mathbb{R}_{>0}=(0,\infty)$.

  * •

Let the set of complex numbers be denoted by $\mathbb{C}$.

  * •

We denote the set of integers $\\{i,i+1,i+2,\dots,i+k\\}$ as
$\mathbb{N}_{[i,i+k]}$.

  * •

The number of $k$-element subsets of an $n$-element set is denoted
$\binom{n}{k}$.

  * •

Let $(u,v)$ where $u\in\mathbb{R}^{n_{u}}$ and $v\in\mathbb{R}^{n_{v}}$ denote
the column vector $(u^{T},v^{T})^{T}$.

  * •

The cardinality of a set $\mathcal{J}$ is denoted as
$\\#\left(\mathcal{J}\right)$.

  * •

The identity matrix of dimension $n$ is denoted by $\mathbb{I}_{n}$ and a
matrix of dimension $m$ by $n$ with all elements $1$ is denoted by
$\mathbf{{1}}_{m\times n}$.

  * •

A diagonal matrix with elements $d_{i}$, $i\in\mathbb{N}_{[1,n]}$ is denoted
by $\textrm{diag}(d_{1},d_{2},\dots,d_{n})$.

  * •

Given a symmetric matrix $P$, its maximum (minimum) eigenvalue is denoted by
$\lambda_{\max}(P)$ $(\lambda_{\min}(P))$.

  * •

The infinity norm of a vector $x\in\mathbb{R}^{n}$, is denoted
$|x|:=\underset{i\in\mathbb{N}_{[1,n]}}{\max}\left|x_{i}\right|$ and for a
matrix $A\in\mathbb{R}^{n\times n}$,
$|A|:=\underset{i\in\mathbb{N}_{[1,n]}}{\max}\underset{j\in\mathbb{N}_{[1,n]}}{\sum}|a_{ij}|$,
where $a_{ij}$ is the row $i$-th and column $j$-th element of matrix $A$.

  * •

A continuous function $\alpha:\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ is a
class $\mathcal{K}$ function, if it is strictly increasing and $\alpha(0)=0$;
additionally, if $\alpha(r)\to\infty$ as $r\to\infty$, then $\alpha$ is a
class $\mathcal{K}_{\infty}$ function. A continuous function
$\beta:\mathbb{R}_{\geq 0}\times\mathbb{R}_{\geq 0}\to\mathbb{R}_{\geq 0}$ is
a class $\mathcal{KL}$ function, if: (i) $\beta(.,s)$ is a class $\mathcal{K}$
function for each $s\geq 0$; (ii) $\beta(r,.)$ is non-increasing and (iii)
$\beta(r,s)\to 0$ as $s\to\infty$ for each $r\geq 0$.

##  III Problem statement

We consider the problem of state observation for a class of nonlinear systems
under sensor attacks of the following form

$\displaystyle\dot{x}$ $\displaystyle=$ $\displaystyle
f(x,z,w),\,z=(z_{1},z_{2},\dots,z_{N}),$ $\displaystyle z_{i}$
$\displaystyle=$ $\displaystyle h_{i}(x,w),$ $\displaystyle y_{i}$
$\displaystyle=$ $\displaystyle z_{i}+a_{i},\qquad i\in\mathbb{N}_{[1,N]},$
(1)

where $x\in\mathbb{R}^{n_{x}}$ is the state, $y_{i}\in\mathbb{R}^{n_{i}}$ is
the measured output at sensor $i$, $w\in\mathbb{R}^{n_{u}}$ is a measured
input, $f$ and $h_{i}$ are locally Lipschitz functions and
$a_{i}\in\mathbb{R}^{n_{i}}$ is a possibly unbounded attack signal that cannot
be measured.

###### Assumption 1

Further assumptions about the attack signals $a_{i}$ are

  1. (i)

Sensors $i\in\mathbb{N}_{[1,N]}$ which are not under attack satisfy
$a_{i}(t)=0$, for all $t\geq 0$.

  2. (ii)

Given an index set $\mathcal{I}\subseteq\mathbb{N}_{[1,N]}$, the set of non-
attacked sensors remain constant, i.e. the attack vector
$a=(a_{1},a_{2},\dots,a_{N})\in\mathcal{N}_{I}$, where
$\mathcal{N}_{\mathcal{I}}:=\\{(a_{1},a_{2},\dots,a_{N}):a_{i}(t)=0,\forall
t\geq 0,\forall i\not\in\mathcal{I}\\}$.

$\Box$

In this paper, we derive conditions such that the state $x$ of system (III)
with $N$ outputs can be estimated when $M$ of the sensors have been attacked,
which we term observable under $M$ attacks and formally define below.

###### Definition 1

System (III) is observable under $M$ attacks if for any

  * •

initial conditions $x(0)$, $\bar{x}(0)\in\mathbb{R}^{n_{x}}$,

  * •

measured input $w\in\mathbb{R}^{n_{u}}$,

  * •

index sets $\mathcal{I}_{a}$, $\mathcal{I}_{b}\subset\mathbb{N}_{[1,N]}$ with
not more than $M$ elements,

  * •

attack vectors $a=(a_{1},a_{2},\dots,a_{N})\in\mathcal{N}_{\mathcal{I}_{a}}$,
$\bar{a}=(\bar{a}_{1},\bar{a}_{2},\dots,\bar{a}_{N})\in\mathcal{N}_{\mathcal{I}_{b}}$,

there exists an index set $\mathcal{J}\subset\mathbb{N}_{[1,N]}$ with at least
$N-2M$ elements, such that the output trajectories of system (III) satisfy

$\displaystyle\underline{\alpha}_{y}$
$\displaystyle\left(\left|x(0)-\bar{x}(0)\right|,t\right)$ (2)
$\displaystyle\leq|y_{i}\left(t;x(0),w,a_{i}\right)-y_{i}\left(t;\bar{x}(0),w,\bar{a}_{i}\right)|$
$\displaystyle\qquad\qquad\leq\bar{\alpha}_{y}\left(\left|x(0)-\bar{x}(0)\right|\right),$

for all $i\in\mathcal{J}$, $t\geq 0$, and $\underline{\alpha}_{y}$ is a class
$\mathcal{KL}$ function and $\bar{\alpha}_{y}$ is a class $\mathcal{K}$
function. $\Box$

We have denoted the output trajectories of system $\eqref{eq:system}$
initialized at $x(0)$ for the input $w$ and attack $a_{i}$ as
$y_{i}(t;x(0),w,a_{i})$, for all $i\in\mathbb{N}_{[1,N]}$.

Definition 1 means that when a system (III) is observable under $M$ attacks,
there is at most one initial condition in which system (III) generates a
compatible measured output $y_{i}$ for any given input signal $w$, for at
least $N-2M$ of the measured outputs. This has to be achieved regardless of
which of the $M$ sensors have been compromised and the attack signal $a_{i}$
that has been chosen by the attacker.

##  IV A sufficient condition for observabilty under $M$ attacks

We provide a sufficient condition for system (III) to be observable under $M$
attacks.

###### Theorem 1

For any integer $M\geq 0$, (ii) implies (i):

  1. (i)

System (III) is observable under $M$ attacks.

  2. (ii)

$N>2M$ and, for every set $\mathcal{J}\subset\mathbb{N}_{[1,N]}$ with
$\\#\left(\mathcal{J}\right)\geq N-2M$, there exists a function
$\hat{f}:\mathbb{R}^{n_{x}}\times\mathbb{R}^{\\#\left(\mathcal{J}\right)}\times\mathbb{R}^{\\#\left(\mathcal{J}\right)}\to\mathbb{R}^{n_{x}}$
such that the solution to

$\dot{\hat{x}}_{\mathcal{J}}=\hat{f}\left(\hat{x}_{\mathcal{J}},y_{\mathcal{J}},w\right),$
(3)

and the solution to system (III), respectively satisfy

$\displaystyle\left|x(t)-\hat{x}_{\mathcal{J}}(t)\right|\leq\hat{\beta}$
$\displaystyle\left(\left|x(0)-\hat{x}_{\mathcal{J}}(0)\right|,t\right)$
$\displaystyle+\hat{\gamma}\left(\underset{s\in[0,t)}{\sup}\left|a_{\mathcal{J}}(s)\right|\right),$
(4)

for all $t\geq 0$ and initial conditions $x(0)$,
$\hat{x}_{\mathcal{J}}(0)\in\mathbb{R}^{n_{x}}$, where $\hat{\beta}$ is a
$\mathcal{KL}$ function, $\hat{\gamma}$ is a $\mathcal{K}_{\infty}$ function,
and $a_{\mathcal{J}}$ denotes a stacked vector of $a_{i}$ indexed by
$i\in\mathcal{J}$.

$\Box$

Theorem 1 specifies that the number of available sensors $N$ has to be
strictly more than twice the number of compromised sensors $M$. This is
consistent with the results for linear systems in [1] for continuous-time
systems and [4] for discrete-time systems, as well as in [15] and [14] for
classes of nonlinear systems in continuous and discrete-time, respectively.

Further, condition (ii) means that the estimation error
$e_{\mathcal{J}}:=x-\hat{x}_{\mathcal{J}}$ system constructed out of system
(III) and (3) is input-to-state stable (ISS) [17] with respect to the attack
vector $a_{\mathcal{J}}$. This property can be fulfilled with Luenberger
observers in the case of linear systems (see [1, Section III.B]), and with
high gain observers [18] or circle criterion observers [19] for classes of
nonlinear systems. We will provide a constructive example in our case study in
Section VI.

##  V Algorithm

Using Theorem 1, we formulate the following estimation algorithm to estimate
the states of system (III) when $M$ out of $N$ of its sensors have been
compromised. Our algorithm follows the idea presented in [1], where the
results were derived for linear dynamical systems.

The crux of the algorithm lies in the fact that for each combination of $N-M$
outputs (note that this is greater than $N-2M$ outputs, which satisfies
condition (ii) in Theorem 1), there is one observer which receives attack-free
sensor outputs and hence provides state estimates that converges to the true
state. Further, for each set of these $N-M$ outputs, there is at least one
subset consisting of $N-2M$ outputs which is attack-free. Thus, the observer
which receives the attack-free subset of $N-2M$ outputs will provide a state
estimate which converge to the true one. Therefore, in the algorithm presented
in this section, we employ two banks of observers: one bank of observers
employing $N-M$ outputs, and the other employing $N-2M$ outputs.

Suppose that at most $M$ out of $N$ of system (III)’s outputs can be
compromised and condition (ii) of Theorem III holds. Then, for every set
$\mathcal{S}\subset\mathbb{N}_{[1,N]}$ of $N-M$ elements, an observer which
employs $N-M$ outputs from system (III) is constructed as follows

$\dot{\hat{x}}_{\mathcal{S}}=\hat{f}(\hat{x}_{\mathcal{S}},y_{\mathcal{S}},w),$
(5)

which has an estimation error system that is ISS with respect to the attack
vector $a_{\mathcal{S}}$ as stated in (ii) of Theorem 1. This forms the first
bank of $\binom{N}{N-M}$ observers. We define the consistency measure
$\pi_{\mathcal{S}}$ to be the worst case deviation between the estimate
$\hat{x}_{\mathcal{S}}$ given by (5) and the estimate $\hat{x}_{\mathcal{P}}$
generated in the same manner as (5) for $\mathcal{P}\subset\mathcal{S}$ with
$N-2M$ elements, which is

$\pi_{\mathcal{S}}(t)=\underset{\mathcal{P}\subset\mathcal{S}:\\#(\mathcal{P})=N-2M}{\max}\left|\hat{x}_{\mathcal{S}}(t)-\hat{x}_{\mathcal{P}}(t)\right|.$
(6)

For the set $\mathcal{S}$ in which all the attack vectors are zero, i.e.
$a_{i}(t)=0$, for all $i\in\mathcal{S}$ and $t\geq 0$, all the state estimates
$\hat{x}_{\mathcal{S}}$ and $\hat{x}_{\mathcal{P}}$ will be consistent and
this motivates the choice of the state estimate $\hat{x}$ produced by the
algorithm as follows

$\displaystyle\hat{x}(t)$ $\displaystyle=\hat{x}_{\sigma(t)}(t),$
$\displaystyle\sigma(t)$
$\displaystyle=\underset{\mathcal{S}\subset\mathbb{N}_{[1,N]}:\\#(\mathcal{S})=N-M}{\arg\min}\pi_{\mathcal{S}}(t).$
(7)

We summarize the algorithm (5), (6), (V) in Figure 1 and provide the following
state estimation convergence guarantees.

###### Theorem 2

Consider system (III) with $N$-outputs of which at most $M$ is compromised,
i.e. the attack vector $a$ belongs to $\mathcal{N}_{\mathcal{I}}$, for some
set $\mathcal{I}\subset\mathbb{N}_{[1,N]}$ where $\\#(\mathcal{I})\leq M$.
Assuming that (ii) of Theorem 1 holds, then there exists a class
$\mathcal{KL}$ function $\tilde{\beta}$ such that the solution to system (III)
and the secure state estimation algorithm (5), (6), (V) satisfy

$\left|x(t)-\hat{x}(t)\right|\leq\tilde{\beta}\left(\left|x(0)-\hat{x}(0)\right|,t\right),\;\forall
t\geq 0,$ (8)

for any initial conditions $x(0)$, $\hat{x}_{\mathcal{S}}(0)$,
$\hat{x}_{\mathcal{P}}(0)\in\mathbb{R}^{n_{x}}$. $\Box$

Figure 1: Infrastructure of a secure state estimation algorithm for nonlinear
systems (III).

##  VI Case study: A class of nonlinear systems

We consider a specific form of system (III) as follows:

$\displaystyle\dot{x}$ $\displaystyle=$ $\displaystyle
Ax+\phi(z),\;\phi(z)=\left(\phi_{1}(z_{1}),\phi_{2}(z_{2}),\dots,\phi_{N}(z_{N})\right),$
$\displaystyle z_{i}$ $\displaystyle=$ $\displaystyle
H_{i}x+w_{i},\;i\in\mathbb{N}_{[1,N]},$ $\displaystyle y_{i}$ $\displaystyle=$
$\displaystyle z_{i}+a_{i},$ (9)

where the nonlinearities $\phi_{i}:\mathbb{R}^{n_{i}}\to\mathbb{R}$ are slope-
restricted, i.e.

###### Assumption 2

For $i\in\mathbb{N}_{[1,N]}$, the nonlinearity $\phi_{i}$ satisfies

$\underline{d}_{i}\leq\frac{\phi_{i}(\xi)-\phi_{i}(\psi)}{\xi-\psi}\leq\bar{d}_{i},\;\forall\xi,\psi\in\mathbb{R},\,\xi\neq\psi.$
(10)

$\Box$

For system (VI) with $N$ outputs, of which $M$ can be compromised, we show
that (ii) of Theorem 1 is satisfied by designing each observer (3) in the
following manner for every set $\mathcal{J}\subset\mathbb{N}_{[1,N]}$.

$\displaystyle\dot{\hat{x}}_{\mathcal{J}}$ $\displaystyle=$ $\displaystyle
A\hat{x}_{\mathcal{J}}+\phi(\xi_{\mathcal{J}})+\bar{o}(L_{\mathcal{J}},y_{\mathcal{J}},\hat{x}_{\mathcal{J}},w_{\mathcal{J}}),$
$\displaystyle\xi_{\mathcal{J}}$ $\displaystyle=$ $\displaystyle
H\hat{x}_{\mathcal{J}}+w+\bar{o}(K_{\mathcal{J}},y_{\mathcal{J}},\hat{x}_{\mathcal{J}},w_{\mathcal{J}}),$
(11)

where
$\bar{o}(K_{\mathcal{J}},y_{\mathcal{J}},\hat{x}_{\mathcal{J}},w_{\mathcal{J}})=K_{\mathcal{J}}\left(y_{\mathcal{J}}-\left(H_{\mathcal{J}}\hat{x}_{\mathcal{J}}+w_{\mathcal{J}}\right)\right)$
is an output injection term employing outputs $y_{\mathcal{J}}$, known inputs
$w_{\mathcal{J}}$ and an observer matrix $K_{\mathcal{J}}$ to be designed.
Note that the first two terms in $\xi_{\mathcal{J}}$ use the full $H$ from
system (VI) and all the known inputs $w$, respectively.

###### Proposition 1

Consider system (VI) under Assumption 2. Suppose $N>2M$ and, for every set
$\mathcal{J}\subset\mathbb{N}_{[1,N]}$ with $\\#\left(\mathcal{J}\right)\geq
N-2M$, there exist a matrix $P_{\mathcal{J}}=P_{\mathcal{J}}^{T}>0$, scalars
$\nu_{\mathcal{J}}\geq 0$, $\mu_{\mathcal{J}}\geq 0$ and observer matrices
$K_{\mathcal{J}}$ and $L_{\mathcal{J}}$ such that the following holds

$\left[\begin{array}[]{ccc}\mathcal{A}\left(P_{\mathcal{J}},P_{\mathcal{J}}L_{\mathcal{J}},\nu_{\mathcal{J}}\right)&\mathcal{B}\left(P_{\mathcal{J}},K_{\mathcal{J}}\right)&-P_{\mathcal{J}}\\\
\mathcal{B}\left(P_{\mathcal{J}},K_{\mathcal{J}}\right)^{T}&\mathcal{D}(\bar{d})&0\\\
-P_{\mathcal{J}}&0&-\mu_{\mathcal{J}}\mathbb{I}_{n_{\mathcal{J}}}\end{array}\right]\leq
0,$ (12)

where

  * •

$\mathcal{A}\left(P_{\mathcal{J}},P_{\mathcal{J}}L_{\mathcal{J}},\nu_{\mathcal{J}}\right):=$
$P_{\mathcal{J}}\left(A-L_{\mathcal{J}}H_{\mathcal{J}}\right)+\left(A-L_{\mathcal{J}}H_{\mathcal{J}}\right)^{T}P_{\mathcal{J}}+\nu_{\mathcal{J}}\mathbb{I}_{n_{x}}$,

  * •

$\mathcal{B}\left(P_{\mathcal{J}},K_{\mathcal{J}}\right):=P_{\mathcal{J}}+\left(H-K_{\mathcal{J}}H_{\mathcal{J}}\right)^{T}$,

  * •

$\mathcal{D}(\bar{d}):=-2\,\textrm{diag}\left(\bar{d}_{1}^{-1},\bar{d}_{2}^{-1},\dots,\bar{d}_{N}^{-1}\right)$,

  * •

$n_{\mathcal{J}}:=\underset{i\in\mathcal{J}}{\sum}n_{i}$.

Then, (ii) of Theorem 1 holds. $\Box$

Inequality (12) is a linear matrix inequality (LMI) in $P_{\mathcal{J}}$,
$P_{\mathcal{J}}L_{\mathcal{J}}$, $\nu_{\mathcal{J}}$, $K_{\mathcal{J}}$ and
$\mu_{\mathcal{J}}$, which can be solved efficiently using computational
tools. The design we have used here was first introduced as the circle
criterion observer in [19], which can be tuned to attenuate measurement noise
and input disturbances according to the design in [20]. Here, we have adapted
the design such that the observer (VI) is robust with respect to the attack
vector $a_{\mathcal{J}}$ in the sense of (ii).

##  VII Application: Secure monitoring for the voltage regulation of a power
distribution network

A typical low voltage power distribution network (shown in Figure 2) would
consist of $N$ customers feeding into the distribution network in a line
configuration, with the smart secondary substation at the head of the line.
The substation functions as a monitoring center, sending the desired set-point
voltage $\bar{v}$ to each local controller $\Sigma_{i}$, such that the
voltages received by each customer $v_{i}$ is regulated to operate in a safe
operating range, i.e. for a given $\delta>0$,

$\bar{v}-\delta\leq v_{i}(t)\leq\bar{v}+\delta,\qquad\forall t\geq 0.$ (13)

For each customer $i\in\mathbb{N}_{[1,N]}$, the received voltage level is
$v_{i}$ and the voltage level at the point of connection with the distribution
line is $v^{\prime}_{i}$, with a corresponding line impedance
$Z^{\prime}_{i}=R^{\prime}_{i}+jX^{\prime}_{i}$ in between customer $i$ and
the connection point on the distribution line, where
$R^{\prime}_{i}\in\mathbb{R}_{\geq 0}$ is the resistance and
$X^{\prime}_{i}\in\mathbb{R}_{\geq 0}$ is the reactance. In between each
connection point, the corresponding line impedance is $Z_{i}=R_{i}+jX_{i}$,
where $R_{i}\in\mathbb{R}_{\geq 0}$ is the resistance and
$X_{i}\in\mathbb{R}_{\geq 0}$ is the reactance. Each customer has a load which
can consume reactive $q_{c,i}$ and active powers $\rho_{c,i}$, independently
of the generated reactive $q_{g,i}$ and active powers $\rho_{g,i}$.

In [21], a class of sector-bounded droop controllers $\Sigma_{i}$ which uses
local measurements $v_{i}$ were shown to regulate the voltages $v_{i}$ such
that the safety constraint (13) is satisfied. This is achieved via appropriate
injection of reactive power $q_{g,i}$ by each local controller $\Sigma_{i}$ to
regulate the flow of active $P_{i}$ and reactive $Q_{i}$ powers, under the
assumption that the net injected active power $\rho_{i}$ and the reactive
power $q_{c,i}$ consumed by customer $i$ is bounded and the bounds are known.

Figure 2: Infrastructure of a low-voltage grid. Voltage regulation is achieved
via local controllers $\Sigma_{i}$, for $i\in\mathbb{N}_{[1,N]}$, with the
monitoring center (situated at the substation) receiving potentially corrupted
measurements of $v_{i}$.

We are now concerned with the security problem where the measurements of the
voltages $v_{i}$ received at the monitoring center situated at the substation
has been maliciously corrupted. We model this measurement corruption with an
additive attack signal $\alpha_{i}:\mathbb{R}_{\geq 0}\to\mathbb{R}$ which is
potentially unbounded, as follows

$\hat{y}_{i}=v_{i}+\alpha_{i}.$ (14)

This is a major issue as the presence of the attack signal $\alpha_{i}$ would
mislead the monitoring center into thinking that the safety constraint (13)
has been violated and thus a false alarm is raised and possibly triggering
unwarranted operator actions.

Our solution is to employ the results in the previous sections to estimate the
voltages $v_{i}$, given that $M$ out of $N$ of the measurements $y_{i}$ are
maliciously manipulated. To this end, we model the power flow in the
distribution grid as done in [21] using the linearized DistFlow model [22] and
assume that the droop controllers $\Sigma_{i}$ have been designed using the
methodology presented in [21]. The relationship between the power flow and
voltages between key nodes is

$\begin{array}[]{lll}P_{i+1}&=&P_{i}+\rho_{i+1},\\\
Q_{i+1}&=&Q_{i}+q_{i+1},\\\
{v^{\prime}_{i+1}}^{2}&=&{v^{\prime}_{i}}^{2}-2\beta_{i}(P_{i},Q_{i}),\\\
{v^{\prime}_{i}}^{2}&=&{{v}_{i}}^{2}-2{\beta}^{{}^{\prime}}_{i-1}(\rho_{i},q_{i}),\end{array}$
(15)

where $P_{i}$ and $Q_{i}$ are the respective total active and reactive powers
flowing from customer $i$ to customer $i+1$; $\rho_{i}:=\rho_{g,i}-\rho_{c,i}$
and $q_{i}:=q_{g,i}-q_{c,i}$ are the net injection of the respective active
and reactive power into the distribution line from customer $i$;
$\beta_{i}(r,s):=R_{i}r+X_{i}s$ and
$\beta^{\prime}_{i}(r,s):=R^{\prime}_{i}r+X^{\prime}_{i}s$ with
$\beta^{\prime}_{-1}(r,s)=0$ for all $r,s\in\mathbb{R}$.

Each local controller $\Sigma_{i}$ actuated by the inverter can generate
reactive power $q_{g,i}$ as follows

$\dot{q}_{g,i}=-\frac{1}{\tau_{i}}q_{g,i}+\frac{1}{\tau_{i}}K_{i}(\bar{v}^{2}-v_{i}^{2}),$
(16)

where $\tau_{i}\in\mathbb{R}_{>0}$ is the time-constant of the inverter’s
response, $\bar{v}\in\mathbb{R}$ is the reference voltage communicated to each
customer $i$ and the droop function $K_{i}(w)$ is a static mapping from the
difference of the squared voltages $w$ to the set-point for the reactive
power. We choose the droop function $K_{i}(w)$ to be a piecewise saturation
function considered in [23] which takes the following form:

$K_{i}(w):=\left\\{\begin{array}[]{ll}-\bar{Q}_{i},&w\leq w_{\min,i},\\\
-\left(1-\frac{w-w_{\min,i}}{w_{m,i}-w_{\min,i}}\right)\bar{Q}_{i}&w\in(w_{\min,i},w_{m,i}],\\\
0,&w\in(w_{m,i},w_{n,i}],\\\
\left(\frac{w-w_{n}}{w_{\max,i}-w_{n,i}}\right)\bar{Q}_{i}&w\in(w_{n,i},w_{\max,i}],\\\
\bar{Q}_{i},&w>w_{\max,i},\end{array}\right.$ (17)

where $w_{\min,i}\leq w_{m,i}\leq 0\leq w_{n,i}\leq w_{\max,i}$ are design
parameters, $\bar{Q}_{i}\in\mathbb{R}_{\geq 0}$ is the saturation limit of the
$i$-th inverter satisfying
$\bar{Q}_{i}=\sqrt{\bar{s}_{i}^{2}-\rho_{g,i}^{2}}$, where
$\bar{s}_{i}\in\mathbb{R}$ is the maximum apparent power of the $i$-th
inverter. The design parameters $w_{\min,i}$, $w_{\max,i}$, $w_{m,i}$,
$w_{n,i}$ are chosen such that

$d_{i}:=\min\left\\{\begin{array}[]{cc}\frac{\bar{Q}_{i}}{w_{\max,i}-w_{n,i}},\frac{\bar{Q}_{i}}{w_{m,i}-w_{\min,i}}\end{array}\right\\}$
(18)

satisfies [21, Theorem 6] such that the safety constraint (13) is met. We
employ the same change in state coordinates as done in [21] such that the
distribution model (15), controllers (16), and measurements received at the
monitoring center (14) can be written in the form of (VI) by choosing

  * •

the state $x=\left(q_{g,1},q_{g,2},\dots,q_{g,N}\right)$,

  * •

$z_{i}:={\bar{v}}^{2}-v_{i}^{2}$,

  * •

the known input
$w_{i}=\phi_{i}(\rho,q_{c})+{\bar{v}}^{2}-{v^{\prime}}_{0}^{2}$, where
$\phi_{i}(\rho,q_{c}):=\underset{j\in\mathbb{N}_{[0,i-1]}}{\sum}\psi_{j}(\rho,q_{c})+\\!\\!\\!\underset{j\in\mathbb{N}_{[0,i-2]}}{\sum}2{\beta}^{{}^{\prime}}_{j}(\rho_{j+1},q_{c,j+1})$
and

$\displaystyle\psi_{j}(\rho,q_{c})$
$\displaystyle:=2X_{j}\underset{k\in\mathbb{N}_{[j+1,N]}}{\sum}q_{c,k}-2R_{j}\underset{k\in\mathbb{N}_{[j+1,N]}}{\sum}\rho_{k}$
$\displaystyle-2{\beta^{\prime}}_{j}(\rho_{j+1},q_{c,j+1}),$

where $\beta^{\prime}_{j}$ is from (15),

  * •

the attack signal $a_{i}=2v_{i}\alpha_{i}-\alpha_{i}^{2}$, where $\alpha_{i}$
comes from (14),

  * •

$H_{i}$ to be the rows of the matrix

$\displaystyle H$
$\displaystyle=-2\left(\begin{array}[]{ccccc}X_{0}&X_{0}&\dots&X_{0}\\\
\star&\left(X_{0}+X_{1}\right)&\dots&\left(X_{0}+X_{1}\right)\\\
\vdots&\ddots&\ddots&\vdots\\\
\star&\dots&\star&\underset{i\in\mathbb{N}_{[0,N-1]}}{\sum}X_{i}\end{array}\right)$
$\displaystyle-2\textrm{diag}\left(X^{\prime}_{0},\dots,X^{\prime}_{N-1}\right),$

where $\star$ denotes a block component of a symmetric matrix,

  * •

$A=\textrm{diag}\left(-1/\tau_{1},-1/\tau_{2},\dots,-1/\tau_{N}\right)$,

  * •

$\phi_{i}(z_{i})=\tau_{i}^{-1}K_{i}(z_{i})$, which satisfies Assumption 2 with
$\underline{d}_{i}=0$ and $\bar{d}_{i}=d_{i}/\tau_{i}$, where $d_{i}$ is
defined in (18).

To recapitulate, given that the monitoring center sits remotely at the
substation, the objective is to estimate the voltages $v_{i}$, given that the
monitoring center only has access to the measurements $y_{i}$,
$i\in\mathbb{N}_{[1,N]}$, where $M$ out of $N$ of these measurements may be
corrupted. The main idea is to first estimate the states $x$ of all the
controllers $\Sigma_{i}$, $i\in\mathbb{N}_{[1,N]}$, then estimate the voltages
$v_{i}$ via

$\hat{v}_{i}(t)^{2}=-H_{i}\hat{x}(t)-\psi_{i}(\rho,q_{c})+{v^{\prime}}^{2}_{0},$
(19)

where $\hat{x}$ is the state estimate provided by the secure estimation
algorithm described in Section V; $\psi$ and ${v^{\prime}}^{2}_{0}$ are known.
We have kept the squared form of the voltage $\hat{v}_{i}^{2}$ due to the
distribution model (15) used. We provide the following guarantee.

###### Proposition 2

Consider the distribution model (15) and controllers (16) with measurements
(14) where $a_{\mathcal{I}}$ belongs to $\mathcal{N}_{\mathcal{I}}$ for some
unknown set $\mathcal{I}\subset\mathbb{N}_{[1,N]}$ with at most $M$ elements.
Suppose $N>2M$ and for every $\mathcal{J}\subset\mathbb{N}_{[1,N]}$ with
$\\#\left(\mathcal{J}\right)\geq N-2M$, there exist a matrix
$P_{\mathcal{J}}=P_{\mathcal{J}}^{T}>0$, scalars $\nu\geq 0$, $\mu_{a}\geq 0$
and observer matrices $K_{\mathcal{J}}$ and $L_{\mathcal{J}}$ such that (12)
holds. Then, using the secure state estimation algorithm (5), (6), (V), the
estimated squared voltages $\hat{v}_{i}^{2}$ computed according to (19)
converges to to the true squared voltages $v_{i}^{2}$ as follows

$\left|v_{i}(t)^{2}-\hat{v}_{i}(t)^{2}\right|\leq\beta_{v}\left(\left|x(0)-\hat{x}(0)\right|,t\right),$
(20)

for all $t\geq 0$, $i\in\mathbb{N}_{[1,N]}$, initial conditions
$q_{g,i}(0)\in\mathbb{R}$, where
$x(0)=\left(q_{g,1}(0),q_{g,2}(0),\dots,q_{g,N}(0)\right)$,
$\hat{x}(0)=\left(\hat{q}_{g,1}(0),\hat{q}_{g,2}(0),\dots,\hat{q}_{g,N}(0)\right)$
and $\beta_{v}$ is a class $\mathcal{KL}$ function.

$\Box$

##  VIII Conclusions and future work

We introduced a new definition of observability for nonlinear systems in which
a subset of the outputs can be manipulated maliciously. A sufficient condition
such that asymptotic state reconstruction can be achieved in the presence of
sensor attacks is provided, which requires building a bank of observers with
an ISS property. A secure state estimation algorithm is proposed which shows
that the framework used for linear continuous time systems in our earlier work
[1] can be used for nonlinear systems as well. A systematic method for
designing the observers is proposed for a class of nonlinear systems and we
showed the relevance of this work in the monitoring of a power distribution
network. Future work includes reducing the computational resources needed in
terms of time and number of observers required.

###  -A Proof of Theorem 1

(ii) implies (i): Suppose to the contrary that (ii) is true, but (i) is false,
i.e. there exist initial conditions $x(0)$, $\bar{x}(0)\in\mathbb{R}^{n_{x}}$,
sets $\mathcal{I}_{a}$, $\mathcal{I}_{b}\subset\mathbb{N}_{[1,N]}$ where
$\\#\left(\mathcal{I}_{a}\right)\leq M$ and
$\\#\left(\mathcal{I}_{b}\right)\leq M$, input $w$ and attack vectors
$a\in\mathcal{N}_{\mathcal{I}_{a}}$, $\bar{a}\in\mathcal{N}_{\mathcal{I}_{b}}$
and an index set $\mathcal{J}\subset\mathbb{N}_{[1,N]}$ with
$\\#\left(\mathcal{J}\right)\geq N-2M$ such that for all $i\in\mathcal{J}$

$\displaystyle|y_{i}\left(t;x(0),w,a_{i}\right)$ $\displaystyle-
y_{i}\left(t;\bar{x}(0),w,\bar{a}_{i}\right)|$
$\displaystyle>\bar{\alpha}_{y}\left(\left|x(0)-\bar{x}(0)\right|\right),\qquad\forall
t\geq 0,$ (21)

and/or

$\displaystyle|y_{i}\left(t;x(0),w,a_{i}\right)$ $\displaystyle-
y_{i}\left(t;\bar{x}(0),w,\bar{a}_{i}\right)|$
$\displaystyle<\underline{\alpha}_{y}\left(\left|x(0)-\bar{x}(0)\right|,t\right),\qquad\forall
t\geq 0,$ (22)

where $\underline{\alpha}_{y}$ is a $\mathcal{KL}$ function and $\bar{\alpha}$
is a $\mathcal{K}_{\infty}$ function.

First, note that the solution to (III) satisfies the following for
$i\in\mathbb{N}_{[1,N]}$

$\displaystyle|y_{i}(t;x(0),$ $\displaystyle
w,a_{i})-y_{i}\left(t;\bar{x}(0),w,\bar{a}_{i}\right)|$ $\displaystyle\leq
l_{i}\left|x(t;x(0),w,a_{i})-x(t;\bar{x}(0),w,\bar{a}_{i})\right|,$ (23)

where $l_{i}\geq 0$ is the Lipschitz constant of the output function $h_{i}$
from system (III).

Consider the index set
$\mathcal{J}:=\mathbb{N}_{[1,N]}/\\{\mathcal{I}_{a}\cup\mathcal{I}_{b}\\}$,
where $a_{i}=0$ and $\bar{a}_{i}=0$, for all $i\in\mathcal{J}$. We can view
$x(t;\bar{x}(0),w,\bar{a}_{i})$ as a solution to (3) with
$\hat{f}\left(\hat{x}_{\mathcal{J}},y_{\mathcal{J}}|_{a_{\mathcal{J}}=0},w\right)=f(x,z,w)$,
which is a copy of system (III)’s dynamics, initialized at $\bar{x}(0)$. Using
(ii), we have from (-A) that for all $i\in\mathcal{J}$

$\displaystyle|y_{i}\left(t;x(0),w,a_{i}\right)$ $\displaystyle-
y_{i}\left(t;\bar{x}(0),w,\bar{a}_{i}\right)|$
$\displaystyle\leq\alpha_{i}\left(\left|x(0)-\bar{x}(0)\right|\right),\qquad\forall
t\geq 0,$ (24)

where $\alpha_{i}(r):=l_{i}\hat{\beta}(r,0)$ is a $\mathcal{K}_{\infty}$
function and $\hat{\beta}$ is a $\mathcal{KL}$ from (ii). According to (-A),
$|y_{i}\left(t;x(0),w,a_{i}\right)-y_{i}\left(t;\bar{x}(0),w,\bar{a}_{i}\right)|=0$
when $|x(0)-\bar{x}(0)|=0$, which contradicts (-A) and (-A). Therefore, (ii)
implies (i).

###  -B Proof of Theorem 2

Let $\bar{\mathcal{I}}:=\mathbb{N}_{[1,N]}\backslash\mathcal{I}$ and consider
the consistency measure for the set $\bar{\mathcal{I}}$.

$\displaystyle\pi_{\bar{\mathcal{I}}}(t)$
$\displaystyle=\underset{\mathcal{P}\subset\bar{\mathcal{I}}:\\#(\mathcal{P})=N-2M}{\max}\left|\hat{x}_{\bar{\mathcal{I}}}(t)-\hat{x}_{\mathcal{P}}(t)\right|$
$\displaystyle=\underset{\mathcal{P}\subset\bar{\mathcal{I}}:\\#(\mathcal{P})=N-2M}{\max}\left|\hat{x}_{\bar{\mathcal{I}}}(t)-x(t)+x(t)-\hat{x}_{\mathcal{P}}(t)\right|$
$\displaystyle\leq\left|\hat{x}_{\bar{\mathcal{I}}}(t)-x(t)\right|+\underset{\mathcal{P}\subset\bar{\mathcal{I}}:\\#(\mathcal{P})=N-2M}{\max}\left|x(t)-\hat{x}_{\mathcal{P}}(t)\right|.$
(25)

Note that $a_{i}(t)=0$, for all $t\geq 0$ and $i\in\bar{\mathcal{I}}$.
Further, for every $\mathcal{P}\subset\bar{\mathcal{I}}$, where
$\\#(\mathcal{P})=N-2M$, we also have that $a_{i}(t)=0$, for all $t\geq 0$ and
$i\in{\mathcal{P}}$. Therefore, by assumption that (ii) of Theorem 1 holds, we
have that for any $\mathcal{X}\subset\mathbb{N}_{[1,N]}$ (either
$\mathcal{X}=\bar{\mathcal{I}}$ or $\mathcal{X}={\mathcal{P}}$)

$\begin{array}[]{lll}\left|\hat{x}_{\mathcal{X}}(t)-x(t)\right|&\leq&\beta_{\mathcal{X}}\left(\left|\hat{x}_{\mathcal{X}}(0)-x(0)\right|,t\right),\;\forall
t\geq 0,\end{array}$ (26)

for all $\hat{x}_{\mathcal{X}}(0)$, $x(0)\in\mathbb{R}^{n_{x}}$, where
$\beta_{\mathcal{X}}$ is a class $\mathcal{KL}$ function.

We also observe that for every set $\mathcal{S}$ with $\\#(\mathcal{S})=N-M$,
we have at least one set $\bar{\mathcal{P}}\subset\mathcal{S}$ with
$\\#(\bar{\mathcal{P}})=N-2M$ where $a_{i}(t)=0$, for all $t\geq 0$ and
$i\in\bar{\mathcal{P}}$. Hence, assuming that (ii) of Theorem 1 is satisfied,
we have that

$\begin{array}[]{lll}\left|\hat{x}_{\bar{\mathcal{P}}}(t)-x(t)\right|&\leq&\beta_{\bar{\mathcal{P}}}\left(\left|\hat{x}_{\bar{\mathcal{P}}}(0)-x(0)\right|,t\right),\;\forall
t\geq 0,\end{array}$ (27)

for all $\hat{x}_{\bar{\mathcal{P}}}(0)$, $x(0)\in\mathbb{R}^{n_{x}}$, where
$\beta_{\bar{\mathcal{P}}}$ is a class $\mathcal{KL}$ function.

Moreover, using the fact that

$\begin{array}[]{lll}\pi_{\sigma(t)}(t)&=&\underset{\mathcal{P}\subset\sigma:\\#(\mathcal{P})=N-2M}{\max}\left|\hat{x}_{\sigma(t)}(t)-\hat{x}_{\mathcal{P}}(t)\right|\\\
&\geq&\left|\hat{x}_{\sigma(t)}-\hat{x}_{\bar{\mathcal{P}}}(t)\right|,\end{array}$
(28)

we obtain

$\begin{array}[]{lll}\left|x(t)-\hat{x}_{\sigma(t)}(t)\right|&=&\left|x(t)-\hat{x}_{\bar{\mathcal{P}}}+\hat{x}_{\bar{\mathcal{P}}}-\hat{x}_{\sigma(t)}(t)\right|\\\
&\leq&\left|x(t)-\hat{x}_{\bar{\mathcal{P}}}\right|+\left|\hat{x}_{\bar{\mathcal{P}}}-\hat{x}_{\sigma(t)}(t)\right|\\\
&\leq&\left|x(t)-\hat{x}_{\bar{\mathcal{P}}}\right|+\pi_{\sigma(t)}(t)\\\
&\leq&\left|x(t)-\hat{x}_{\bar{\mathcal{P}}}\right|+\pi_{\bar{\mathcal{I}}}(t),\end{array}$
(29)

where we have obtained the second to last inequality with (28) and the last
inequality by definition of $\pi_{\sigma(t)}$.

Therefore, using (25), (26) and (27),

$\begin{array}[]{ll}\left|x(t)-\hat{x}_{\sigma(t)}(t)\right|\leq&\beta_{\bar{\mathcal{P}}}\left(\left|\hat{x}_{\bar{\mathcal{P}}}(0)-x(0)\right|,t\right)\\\
&+\beta_{\bar{\mathcal{I}}}\left(\left|\hat{x}_{\bar{\mathcal{I}}}(0)-x(0)\right|,t\right)\\\
&+\bar{\beta}_{{\mathcal{P}}}\left(\left|\hat{x}_{{\mathcal{P}}}(0)-x(0)\right|,t\right).\end{array}$
(30)

where
$\bar{\beta}:=\underset{\mathcal{P}\subset\bar{\mathcal{I}}:\\#(\mathcal{P})=N-2M}{\max}\beta_{\mathcal{P}}$
which is also a $\mathcal{KL}$ function.

By a property of class $\mathcal{KL}$ functions [24, Lemma 5.3], we know that
there exist class $\mathcal{K}_{\infty}$ functions
$\alpha_{\bar{\mathcal{P}}}$, $\alpha_{\bar{\mathcal{I}}}$ and
$\alpha_{{\mathcal{P}}}$, as well as positive constants
$\lambda_{\bar{\mathcal{P}}}$, $\lambda_{\bar{\mathcal{I}}}$ and
$\lambda_{{\mathcal{P}}}>0$ such that

$\begin{array}[]{ll}\left|x(t)-\hat{x}_{\sigma(t)}(t)\right|\leq&\alpha_{\bar{\mathcal{P}}}\left(\left|\hat{x}_{\bar{\mathcal{P}}}(0)-x(0)\right|\right)e^{-\lambda_{\bar{\mathcal{P}}}t}\\\
&+\alpha_{\bar{\mathcal{I}}}\left(\left|\hat{x}_{\bar{\mathcal{I}}}(0)-x(0)\right|\right)e^{-\lambda_{\bar{\mathcal{I}}}t}\\\
&+\alpha_{{\mathcal{P}}}\left(\left|\hat{x}_{{\mathcal{P}}}(0)-x(0)\right|\right)e^{-\lambda_{{\mathcal{P}}}t},\,\forall
t\geq 0.\end{array}$ (31)

Hence, we obtain (8) as desired with
$\tilde{\beta}:=3\max\left\\{\alpha_{\bar{\mathcal{P}}}\left(\left|\hat{x}_{\bar{\mathcal{P}}}(0)-x(0)\right|\right),\,\alpha_{\bar{\mathcal{I}}}\left(\left|\hat{x}_{\bar{\mathcal{I}}}(0)-x(0)\right|\right),\,\right.$
$\left.\alpha_{{\mathcal{P}}}\left(\left|\hat{x}_{{\mathcal{P}}}(0)-x(0)\right|\right)\right\\}e^{-\lambda
t}$, where
$\lambda:=\min\left\\{\lambda_{\bar{\mathcal{P}}},\lambda_{\bar{\mathcal{I}}},\lambda_{{\mathcal{P}}}\right\\}$.

###  -C Proof of Proposition 1

Let the state estimation error for every set
$\mathcal{J}\subset\mathbb{N}_{[1,N]}$ be
$\tilde{x}_{\mathcal{J}}:=x-\hat{x}_{\mathcal{J}}$. The state estimation error
system is

$\displaystyle\dot{\tilde{x}}_{\mathcal{J}}$
$\displaystyle=\left(A-L_{\mathcal{J}}H_{\mathcal{J}}\right)\tilde{x}_{\mathcal{J}}+\phi(z)-\phi(\xi_{\mathcal{J}})-L_{\mathcal{J}}a_{\mathcal{J}}.$
(32)

Since the nonlinearity $\phi$ satisfies Assumption 2, there exists
$\delta_{i}(t)\in\left[\underline{d}_{i},\bar{d}_{i}\right]$, for
$i\in\mathbb{N}_{[1,N]}$ such that

$\phi(z)-\phi(\xi_{\mathcal{J}})=\delta(t)\eta_{\mathcal{J}}-\delta(t)K_{\mathcal{J}}a_{\mathcal{J}},$

where
$\delta(t):=\textrm{diag}\left(\delta_{1}(t),\delta_{2}(t),\dots,\delta_{N}(t)\right)$
and
$\eta_{\mathcal{J}}:=\left(H-K_{\mathcal{J}}H_{\mathcal{J}}\right)\tilde{x}_{\mathcal{J}}$.
Then the state estimation error system is

$\dot{\tilde{x}}_{\mathcal{J}}=\left(A-L_{\mathcal{J}}H_{\mathcal{J}}\right)\tilde{x}_{\mathcal{J}}+\delta(t)\eta_{\mathcal{J}}-\left(\delta(t)K_{\mathcal{J}}+L_{\mathcal{J}}\right)a_{\mathcal{J}}.$
(33)

We are now ready to show that observer (VI) satisfies (ii) of Theorem 1 using
a candidate Lyapunov function
$V_{\mathcal{J}}(\tilde{x}_{\mathcal{J}})=\tilde{x}_{\mathcal{J}}^{T}P_{\mathcal{J}}\tilde{x}_{\mathcal{J}}$,
where $P_{\mathcal{J}}=P_{\mathcal{J}}^{T}>0$ satisfies (12). The time
derivative of $V_{\mathcal{J}}(\tilde{x}_{\mathcal{J}})$ along the solutions
of the state estimation error system (33) is

$\dot{V}\left(\tilde{x}_{\mathcal{J}}\right)=\chi_{\mathcal{J}}^{T}\left[\begin{array}[]{ccc}P_{\mathcal{J}}\tilde{A}_{\mathcal{J}}+\tilde{A}_{\mathcal{J}}^{T}P_{\mathcal{J}}&P_{\mathcal{J}}&-P_{\mathcal{J}}\\\
P_{\mathcal{J}}&0&0\\\
-P_{\mathcal{J}}&0&0\end{array}\right]\chi_{\mathcal{J}},$ (34)

where
$\chi_{\mathcal{J}}=\left(\tilde{x}_{\mathcal{J}},\delta(t)\eta_{\mathcal{J}},\left(\delta(t)K_{\mathcal{J}}+L_{\mathcal{J}}\right)a_{\mathcal{J}}\right)$
and $\tilde{A}_{\mathcal{J}}:=A-L_{\mathcal{J}}H_{\mathcal{J}}$.

Applying (12), we obtain

$\displaystyle\dot{V}\left(\tilde{x}_{\mathcal{J}}\right)\leq$
$\displaystyle-\nu_{\mathcal{J}}|\tilde{x}_{\mathcal{J}}|^{2}-2\eta_{\mathcal{J}}^{T}\delta(t)\eta_{\mathcal{J}}$
$\displaystyle+2\eta_{\mathcal{J}}^{T}\delta(t)^{T}\textrm{diag}\left(1/\bar{d}_{1},1/\bar{d}_{2},\dots,1/\bar{d}_{N}\right)\delta(t)\eta_{\mathcal{J}}$
$\displaystyle+\mu_{a}\left|\delta(t)K_{\mathcal{J}}+L_{\mathcal{J}}\right|^{2}\left|a_{\mathcal{J}}\right|^{2}.$
(35)

We first examine the second and third terms on the right hand side of the
inequality component by component, i.e. for $i\in\mathbb{N}_{[1,N]}$,
$\delta_{i}(t)-\delta_{i}(t)^{2}/\bar{d}_{i}=\delta_{i}(t)\left(1-\delta_{i}(t)/\bar{d}_{i}\right)\geq
0$, as $\delta_{i}(t)>0$ and $1-\delta_{i}(t)/\bar{d}_{i}\geq 0$ by Assumption
2. Next, $\left|\delta(t)K_{\mathcal{J}}+L_{\mathcal{J}}\right|^{2}\leq
2\left|\delta(t)K_{\mathcal{J}}\right|^{2}+2\left|L_{\mathcal{J}}\right|^{2}$
by Young’s inequality and we obtain

$\displaystyle\dot{V}\left(\tilde{x}_{\mathcal{J}}\right)\leq$
$\displaystyle-\nu_{\mathcal{J}}|\tilde{x}_{\mathcal{J}}|^{2}+\mu_{a}\left(2\bar{d}^{2}\left|K_{\mathcal{J}}\right|^{2}+2\left|L_{\mathcal{J}}\right|^{2}\right)\left|a_{\mathcal{J}}\right|^{2},$
(36)

where
$\bar{d}:=\max\left\\{\bar{d}_{1},\bar{d}_{2},\dots,\bar{d}_{N}\right\\}$.

By noting that $V_{\mathcal{J}}(\tilde{x}_{\mathcal{J}})$ can be sandwiched as
follows

$\lambda_{\min}\left(P_{\mathcal{J}}\right)\left|\tilde{x}_{\mathcal{J}}\right|^{2}\leq
V_{\mathcal{J}}(\tilde{x}_{\mathcal{J}})\leq\lambda_{\max}\left(P_{\mathcal{J}}\right)\left|\tilde{x}_{\mathcal{J}}\right|^{2},$
(37)

and using the comparison principle, the solution to (36) satisfies

$\displaystyle V\left(\tilde{x}_{\mathcal{J}}\right)$ $\displaystyle\leq
e^{-\lambda_{\mathcal{J}}t}V\left(\tilde{x}_{\mathcal{J}}(0)\right)+{\alpha_{\mathcal{J}}}\int_{0}^{t}e^{-\lambda_{\mathcal{J}}(t-s)}\left|a_{\mathcal{J}}(s)\right|^{2}ds,$
(38)

where
$\lambda_{\mathcal{J}}:=\nu_{\mathcal{J}}/\lambda_{\max}(P_{\mathcal{J}})$,
$\alpha_{\mathcal{J}}:=2\mu_{a}\left(\bar{d}^{2}\left|K_{\mathcal{J}}\right|^{2}+\left|L_{\mathcal{J}}\right|^{2}\right)/\lambda_{\max}\left(P_{\mathcal{J}}\right)$.
Since
$\int_{0}^{t}e^{-\lambda_{\mathcal{J}}(t-s)}ds=\left(1-e^{-\lambda_{\mathcal{J}}t}\right)/\lambda_{\mathcal{J}}\leq
1/\lambda_{\mathcal{J}}$, we obtain

$\displaystyle V\left(\tilde{x}_{\mathcal{J}}\right)$ $\displaystyle\leq
e^{-\lambda_{\mathcal{J}}t}V\left(\tilde{x}_{\mathcal{J}}(0)\right)+{\alpha_{\mathcal{J}}/\lambda_{\mathcal{J}}}\underset{s\in[0,t]}{\sup}\left|a_{\mathcal{J}}(s)\right|^{2}.$
(39)

By applying (37) again, we obtain (ii) as desired with
$\hat{\beta}(r,t)=\sqrt{\frac{\lambda_{\max}\left(P_{\mathcal{J}}\right)}{\lambda_{\min}\left(P_{\mathcal{J}}\right)}}e^{-\frac{\lambda_{\mathcal{J}}}{2}t}.r$
and
$\hat{\gamma}(r):=\sqrt{\frac{\alpha_{\mathcal{J}}}{\lambda_{\mathcal{J}}\lambda_{\min}\left(P_{\mathcal{J}}\right)}}r$.

###  -D Proof of Proposition 2

From (15), (16) and (19), we have for $i\in\mathbb{N}_{[1,N]}$

$\begin{array}[]{lll}\left|v_{i}^{2}(t)-\hat{v}_{i}^{2}(t)\right|&\leq&\left|H_{i}\right|\left|{x}(t)-\hat{x}(t)\right|,\\\
&\leq&\left|H_{i}\right|\tilde{\beta}\left(\left|{x}(0)-\hat{x}(0)\right|,t\right),\;t\geq
0,\end{array}$ (40)

where we obtain the last inequality according to Proposition 1 and Theorem 2,
and $\tilde{\beta}$ is a class $\mathcal{KL}$ function from Theorem 2. Hence,
we have shown (20) with $\beta_{v}(r,s)=\left|H_{i}\right|\tilde{\beta}(r,s)$.

## References

  * [1] M. Chong, M. Wakaiki, and J. P. Hespanha, “Observability of linear systems under adversarial attacks,” in 2015 American Control Conference (ACC), pp. 2439–2444, July 2015.
  * [2] H. Sandberg, S. Amin, and K. H. Johansson, “Cyberphysical security in networked control systems: An introduction to the issue,” IEEE Control Systems Magazine, vol. 35, pp. 20–23, Feb 2015.
  * [3] M. S. Chong, H. Sandberg, and A. M. H. Teixeira, “A tutorial introduction to security and privacy for cyber-physical systems,” in 2019 18th European Control Conference (ECC), pp. 968–978, June 2019.
  * [4] H. Fawzi, P. Tabuada, and S. Diggavi, “Secure estimation and control for cyber-physical systems under adversarial attacks,” IEEE Transactions on Automatic Control, vol. 59, no. 6, pp. 1454–1467, 2014.
  * [5] Y. Shoukry and P. Tabuada, “Event-triggered state observers for sparse sensor noise/attacks,” IEEE Transactions on Automatic Control, vol. 61, no. 8, pp. 2079–2091, 2015.
  * [6] Y. Shoukry, M. Chong, M. Wakaiki, P. Nuzzo, A. Sangiovanni-Vincentelli, S. Seshia, J. Hespanha, and P. Tabuada, “SMT-based observer design for cyber-physical systems under sensor attacks,” ACM Transactions on Cyber-Physical Systems, vol. 2, no. 1, p. 5, 2018.
  * [7] C.-H. Xie and G.-H. Yang, “Secure estimation for cyber-physical systems with adversarial attacks and unknown inputs: An $L_{2}$-gain method,” International Journal of Robust and Nonlinear Control, vol. 28, no. 6, pp. 2131–2143, 2018.
  * [8] A.-Y. Lu and G.-H. Yang, “Switched projected gradient descent algorithms for secure state estimation under sparse sensor attacks,” Automatica, vol. 103, pp. 503–514, 2019.
  * [9] A.-Y. Lu and G.-H. Yang, “Secure switched observers for cyber-physical systems under sparse sensor attacks: a set cover approach,” IEEE Transactions on Automatic Control, vol. 64, no. 9, pp. 3949–3955, 2019.
  * [10] L. An and G.-H. Yang, “State estimation under sparse sensor attacks: A constrained set partitioning approach,” IEEE Transactions on Automatic Control, vol. 64, no. 9, pp. 3861–3868, 2018.
  * [11] L. An and G.-H. Yang, “Secure state estimation against sparse sensor attacks with adaptive switching mechanism,” IEEE Transactions on Automatic Control, vol. 63, no. 8, pp. 2596–2603, 2017.
  * [12] Y. Shoukry, P. Nuzzo, N. Bezzo, A. L. Sangiovanni-Vincentelli, S. A. Seshia, and P. Tabuada, “Secure state reconstruction in differentially flat systems under sensor attacks using satisfiability modulo theory solving,” in 2015 54th IEEE Conference on Decision and Control (CDC), pp. 3804–3809, IEEE, 2015.
  * [13] Q. Hu, D. Fooladivanda, Y. H. Chang, and C. J. Tomlin, “Secure state estimation and control for cyber security of the nonlinear power systems,” IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1310–1321, 2017.
  * [14] T. Yang, C. Murguia, M. Kuijper, and D. Nešić, “A robust circle-criterion observer-based estimator for discrete-time nonlinear systems in the presence of sensor attacks,” in 2018 IEEE Conference on Decision and Control (CDC), pp. 571–576, IEEE, 2018.
  * [15] J. Kim, C. Lee, H. Shim, Y. Eun, and J. H. Seo, “Detection of sensor attack and resilient state estimation for uniformly observable nonlinear systems having redundant sensors,” IEEE Transactions on Automatic Control, vol. 64, no. 3, pp. 1162–1169, 2018.
  * [16] S. Nateghi, Y. Shtessel, J.-P. Barbot, and C. Edwards, “Cyber attack reconstruction of nonlinear systems via higher-order sliding-mode observer and sparse recovery algorithm,” in 2018 IEEE Conference on Decision and Control (CDC), pp. 5963–5968, IEEE, 2018.
  * [17] E. D. Sontag, “Input to state stability: Basic concepts and results,” in Nonlinear and optimal control theory, pp. 163–220, Springer, 2008.
  * [18] G. Bornard and H. Hammouri, “A high gain observer for a class of uniformly observable systems,” in Proceedings of the 30th IEEE Conference on Decision and Control, pp. 1494–1496, IEEE, 1991.
  * [19] M. Arcak and P. Kokotović, “Nonlinear observers: a circle criterion design and robustness analysis,” Automatica, vol. 37, no. 12, pp. 1923 – 1930, 2001.
  * [20] M. Chong, R. Postoyan, D. Nešić, L. Kuhlmann, and A. Varsavsky, “A robust circle criterion observer with application to neural mass models,” Automatica, vol. 48, no. 11, pp. 2986–2989, 2012.
  * [21] M. Chong, D. Umsonst, and H. Sandberg, “Local voltage control of an inverter-based power distribution network with a class of slope-restricted droop controllers,” in Procceedings of the 8th IFAC Workshop on Distributed Estimation and Control in Networked Systems, 2019.  To appear.
  * [22] M. Baran and F. Wu, “Network reconfiguration in distribution systems for loss reduction and load balancing,” IEEE Transactions on Power delivery, vol. 4, no. 2, pp. 1401–1407, 1989.
  * [23] F. Andren, B. Bletterie, S. Kadam, P. Kotsampopoulos, and C. Bucher, “On the stability of local voltage control in distribution networks with a high penetration of inverter-based generation,” IEEE Transactions on Industrial Electronics, vol. 62, no. 4, pp. 2519–2529, 2015.
  * [24] C. M. Kellett and A. R. Teel, “Weak converse Lyapunov theorems and control-Lyapunov functions,” SIAM journal on control and optimization, vol. 42, no. 6, pp. 1934–1959, 2004.


# Towards Robust Personalized Dialogue Generation via Order-Insensitive
Representation Regularization

Liang Chen, Hongru Wang, Yang Deng, Wai-Chung Kwan, Zezhong Wang, Kam-Fai Wong
The Chinese University of Hong Kong
MoE Key Laboratory of High Confidence Software Technologies
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

Generating persona consistent dialogue response is important for developing an
intelligent conversational agent. Recent works typically fine-tune large-scale
pre-trained models on this task by concatenating persona texts and dialogue
history as a single input sequence to generate the target response. While
simple and effective, our analysis shows that this popular practice is
seriously affected by Order Sensitivity where different input orders of
persona sentences significantly impact the quality and consistency of
generated response, resulting in severe performance fluctuations (i.e., 29.4%
on GPT2 and 83.2% on BART). To mitigate the order sensitivity problem, we
propose a model-agnostic framework, ORder Insensitive Generation (ORIG), which
enables dialogue models to learn robust representation under different persona
orders and improve the consistency of response generation. Experiments on
Persona-Chat dataset justify the effectiveness and superiority of our method
with two dominant pre-trained models (GPT2 and BART).111The code is available
at https://github.com/ChanLiang/ORIG.

##  1 Introduction

Developing a persona-consistent dialogue model has been one of the key issues
and crucial problems in open-domain dialogue systems (Huang et al., 2020).
Zhang et al. (2018a) define the problem of personalized dialogue generation,
which aims to generate personalized responses based on textually described
persona profiles. Many efforts have been made on developing dialogue models
that generate responses consistent with the provided persona profile Song et
al. (2019, 2020a, 2020b); Wu et al. (2020a).

The recent development in transformer-based pre-trained models Vaswani et al.
(2017); Devlin et al. (2018); Liu et al. (2019); Chen (2020) has led to great
successes in dialogue systems (Wolf et al., 2019; Wu et al., 2020b; Ham et
al., 2020; Kulhánek et al., 2021; Cao et al., 2022; Deng et al., 2022b, c,
2023). Inspired by these successes, previous works incorporate those pre-
trained models in persona-based response generation by concatenating the
dialogue history and persona as input to generate the response in an auto-
regressive manner Song et al. (2021); Liu et al. (2022). However, a fine-tuned
model can generate a high-quality and persona-consistent response in a certain
ordering of personas, while varying this order may lead to a generic and even
inconsistent response as illustrated by the example in Figure 1. We
empirically show that the worst ordering of persona can lead to a 29.4%
decline in BLEU score compared with the best ordering.

Figure 1: A dialog extract from Persona-Chat showing different orderings of
the same persona can lead to different and even inconsistent responses.

Ideally, a well-trained dialogue generation model should be able to generate a
persona-consistent response regardless of the ordering of personas in the
input. We perform experiments and analyses to identify the cause of the
ordering sensitivity. We find that the ordering of persona in the input leads
to different representations of context and response. We also show that the
model can attend to the appropriate persona and generate high-quality
responses under some representations but not under others. This leads to
instability in response generation.

Motivated by the above findings, we propose ORder Insensitive Generation
(ORIG), which is a simple and effective framework that helps models learn more
robust and better representations for different persona orders. More
specifically, we formulate ORIG as a constrained optimization problem, which
optimizes a persona response generation objective under the constraint: given
different orderings of persona, the response representations of the model are
the same. Then we optimize it through a stochastic optimization approach.

Experimental results on the Persona-Chat dataset show that ORIG significantly
improves the robustness of pre-trained models (GPT2 Radford et al. (2019) and
BART Lewis et al. (2020)) under different orderings of input persona, as well
as advances their generation performance.

In summary, our contributions are threefold: (1) We identify the order
sensitivity problem in persona dialogue generation and conduct an empirical
analysis to reveal its underlying reasons. (2) We propose a model-agnostic
framework, ORIG, that helps different persona dialogue models learn robust
representations while achieving better performance. (3) We perform extensive
experiments on the Persona-Chat dataset, showing that ORIG outperforms
previous models and is more robust and less sensitive to different persona
orderings.

##  2 Related Work

Maintaining a consistent persona is essential for building a human-like
dialogue system, where most works regard persona as a set of sentences along
with each dialog (Zhang et al., 2018a; Gu et al., 2019; Song et al., 2019; Wu
et al., 2021; Cao et al., 2022; Deng et al., 2022a). Song et al. (2021)
disentangled the task of persona-based dialogue generation into two sub-tasks:
consistency understanding and dialogue generation while Cao et al. (2022) aims
to alleviate the problem of limited data by data manipulation methods. Despite
satisfactory performance in previous work, the impacts of different orders of
personas are still under-explored, resulting in unstable and inconsistent
responses.

Our work is also related to work on order sensitivity in prompt-based few-shot
learning (Zhao et al., 2021; Lu et al., 2022). Zhao et al. (2021) found that
the different order of training examples in the prompt can cause accuracy to
vary from near chance to state-of-the-art in the few-shot classification
setting. Similarly, order sensitivity for In-context Learning also exists
regardless of model size and the prompt format (Lu et al., 2022).
Distinguishing from them, we focus on order sensitivity in the language
generation task in finetuning setting, especially the impacts of persona
orderings to generate persona-consistent responses.

##  3 Order Sensitivity Problem and Analysis

In this section, we first illustrate the seriousness of the order sensitivity
problem by showing a huge performance fluctuation in persona dialogue models
when fed the same personas in the best and worst orders. Then we analyse why
their performance is volatile to different persona orderings.

To illustrate the problem, we finetune PLMs on the Persona-Chat by
concatenating the persona and dialogue context together to predict the target
response, including GPT2 and BART. After the training converges, we test them
on two settings: (1) the best case: for each test sample, we feed the models
all possible permutations of persona sentences and keep the maximum score for
each sample as the final score; (2) the worst-case: perform the same process
as (1), but take the minimum score. Table 1 shows the results for two models.
Surprisingly, we find the ordering of input persona has a big impact on the
models’ performance: GPT2’s worst case is 29.4% lower than its best case,
while BART’s is 83.2% lower.

Model | BLEU-1 | BLEU-2 | ROUGE | CIDEr
---|---|---|---|---
GPT2-best | 16.79 | 9.25 | 18.44 | 17.56
GPT2-worst | 11.85 | 5.83 | 11.79 | 5.51
BART-best. | 28.17 | 18.29 | 31.07 | 46.53
BART-worst. | 4.73 | 1.99 | 4.37 | 1.34
Table 1:  Performance gap between the best case and worst case when changing
the ordering of input persona.

Moreover, we find that the huge fluctuation in models’ performance is closely
related to the response representation changes caused by different orderings
of input persona sentences. Concretely, we measure the similarity of the
responses representation of the same test sample under different input orders
of persona. We show their token-level similarity in the Table 2 (persona and
context are omitted for brevity), where the bidirectional KL function is
employed as the distance function. Ideally, models should have the consistent
response representation: KL distance between the same response should be zero.
However, their distances are significantly higher than zero. It reveals that
the models behave more likely a left-to-right language model whose
representation is prone to the different orderings of the previous input (e.g.
persona sentences). That is highly undesirable for a robust personalized
dialogue model. Thus, regularization of representation for the response tokens
is necessary to help personalized dialogue models capture order-invariant
representation.

BART |  great(0.185) and(0.105) how(0.312) was(0.289) your(0.124) day(0.304) ?
---|---
Table 2: The token-level representation of the same response can be very
different when the ordering of input persona changes. The value denotes the KL
distance of the same tokens representation returned by the models fed with two
different orderings of persona.

##  4 Method

We introduce the proposed framework, named ORIG: ORder Insensitive Generation
(ORIG). As shown in Figure 2, we transform the persona order-sensitivity
problem as a constrained optimization problem that optimises a persona
dialogue model under the uncertainty of the input persona order.

###  4.1 Problem Formulation

Given the dialogue context $C=\\{u_{1},\dots,u_{m}\\}$ and a set of persona
descriptions $P=\\{p_{1},\dots,p_{n}\\}$, the goal is to generate a
personalized response $r$. Formally, the generation problem can be formulated
as the following chain rule:

$P(r|C,P;\theta)=\prod\nolimits_{t=1}^{T}P\left(r_{t}|r_{1:t-1},C,P;\theta\right)$
(1)

where $\theta$ is the parameters of the dialogue model.

Figure 2: Our proposed framework ORIG

###  4.2 ORIG Framework

According to the analysis in Section 3, the observation reveals that varying
the order of input personas leads to different representations of the dialogue
response, thus resulting in fluctuations in performance.

To learn more robust and consistent representations, we propose the ORIG
framework that complements the response generation process with a constraint:
given the different orderings of a persona, the model’s response
representations need to be the same.

Then the order-insensitive personalized dialogue generation problem is
modelled as the following constrained optimization problem

$\displaystyle\min_{\theta}[-\log P(r|C,P;\theta)]$ (2)
$\displaystyle\textit{s.t.}\quad\mathcal{D}[P(r|C,P;\theta),P(r|C,\hat{P};\theta))]=0$
(3) $\displaystyle(P,C,r)\sim D$ (4)
$\displaystyle\hat{P}\sim\text{Shuffle}(P)$ (5)

where $P(r|C,P;\theta)$ are the model’s predictions over the dialogue
response, D denotes the dialogue corpus, and the function $\mathcal{D}$ is KL
divergence to measure the difference between two distributions, and the
Shuffle operator samples each persona ordering uniformly from the full
permutation of $P$.

###  4.3 Optimization

As for optimization, we first apply the Lagrange multipliers strategy to
convert the constrained problem into an unconstrained problem

$\displaystyle\mathcal{L}_{\theta}=$ $\displaystyle-\log P(r|C,P;\theta)$ (6)
$\displaystyle\left.+\gamma\cdot\mathcal{D}[P(r|C,P;\theta),P(r|C,\hat{P};\theta)]\right.$

where $\gamma$ is the multiplier corresponding to the equality constraints
(3). Then we can update the parameters $\theta$ of dialogue models by
stochastic gradient descent.

##  5 Experiments

###  5.1 Experimental Setups

Datasets We evaluate the models on the Persona-Chat dataset (Zhang et al.,
2018a), where each dialogue session has at least 6 turns of interactions. And
each interaction is conditioned on a persona that is described with 5 profile
sentences.

| Automatic Evaluations | Human Evaluations
---|---|---
Model | BLEU-1 | BLEU-2 | ROUGE | Entropy | CIDEr |  C-score | Flu. | Con. Coh. | Per. Cons.
GPT2 | 13.95 | 7.22 | 14.82 | 6.53 | 10.10 | 0.718 | 1.531 | 1.281 | 1.719
GPT2-ORIG | 14.61 | 7.43 | 14.94 | 6.54 | 10.60 | 0.733 | 1.726 | 1.512 | 1.719
BART | 14.19 | 7.61 | 15.05 | 6.67 | 11.07 | 0.443 | 1.906 | 1.312 | 1.438
BART-ORIG | 14.64 | 7.90 | 15.20 | 6.41 | 13.27 | 0.446 | 1.938 | 1.332 | 1.457
Table 3: Automatic and human evaluation results of applying ORIG on two base
models in the original test set without any modifications on input persona
orders.

Baselines To verify the generality of our framework across different
architectures, we perform experiments on the two most popular pre-trained
architectures: Transformer encoder-decoder (BART) and Transformer decoder
(GPT2).

Implementation Details We choose GPT2 base (117M) and BART base (139M) as the
base models and compare the base models finetuned with classical max
likelihood estimation (MLE) and our proposed ORIG. Our implementation was
based on HuggingFace’s Transformers library Wolf et al. (2020). During
training, the learning rate is set as $2\times 10^{-5}$, and the batch size
for GPT2 and BART is set as 64 and 32, respectively. We trained both models
for 10 epochs with Adam Kingma and Ba (2015) optimizer until they converged.
During decoding, We employ a top-p (p=0.9) Holtzman et al. (2020) plus top-k
(k=50) sampling strategy, which is used to avoid sampling from the unreliable
tail of the distribution (only consider a subset of vocabulary composed of k
words with the highest probability or some most probable words whose sum of
probabilities equals p at each decoding step). The random seed for all
experiments is set to 42.

Evaluation Metrics We perform both automatic and human evaluations. (1)
Automatic metrics: We adopt BLEU Papineni et al. (2002), ROUGE Lin (2004),
EntropyZhang et al. (2018b) and CIDEr Vedantam et al. (2015) for lexical-based
measurement. Following previous work, we also adopt the C-score Madotto et al.
(2019) to indicate the consistency between the generated response and the
input personas. C-score is calculated by the entailment score of a RoBERTa
model finetuned on the DialogueNLI dataset. (2) Human evaluation: We randomly
sampled 200 samples from the test set and ask 3 crowdworkers to rate the
generated responses in the following three aspects: response fluency, context
coherence and persona consistency. The scores $\\{0,1,2\\}$ indicate
unacceptable, acceptable and excellent, respectively. The degree of agreement
during human evaluation is measured by Fleiss’ kappa Fleiss (1971).

Figure 3: Our ORIG improves the mean performance while reducing the variance of both models. Statistics about running each model 100 times on the test set and randomly shuffling the order of the input persona sentences in each run. Model | mean | variance | best | worst
---|---|---|---|---
GPT2 | 14.78 | 0.00193 | 16.79 | 11.85
GPT2-ORIG | 14.93 | 0.00016 | 14.95 | 14.25
BART | 15.01 | 0.01123 | 28.17 | 4.73
BART-ORIG | 15.18 | 0.00532 | 26.44 | 5.80
Table 4:  Statistical results of BLEU-1. The mean and variance are obtained by
running each model 100 times on the test set and randomly shuffling the order
of the input persona sentences in each run. The best case and worst case are
obtained by feeding models the best and worst orderings of personas for every
test sample.

###  5.2 Experimental Results

Improves performance in the original test set Table 3 shows different models’
performance in the original test set without any modifications (for ORIG,
"Shuffle" is used during training but is optional during testing. The Table 3
caption signifies the absence of "Shuffle" during testing. This is to evaluate
if ORIG performs well in the normal setting). From automatic metrics, we can
see base models trained with our ORIG framework outperform the baselines. It
justifies that our framework can be applied to different models to improve
their performance. From human evaluation results, models with ORIG are
superior to others on almost all metircs, especially on GPT2. This is
consistent with the results of automatic metrics. The average kappa value of
the annotation is 0.632, indicating good agreement during human evaluation.

Reduces variance and improves mean and worst-case performance Figure 3 shows
that aside from reducing the variance, ORIG also improves mean and worst-case
performance (detailed results in Table 4) across two models consistently,
especially in GPT2 (the worst case performance is very close to the best
case). We reduce the variance on GPT2 and BART by 91.6% and 51.8%,
respectively. Meanwhile, we improve worst-case performance by 20.3% and 22.6%
on GPT2 and BART respectively. The only drop is the best case. This is because
our distance function $\mathcal{D}$ is unidirectional, which pulls in the two
representations in Equation 3 indiscriminately, causing the best case to go
down and the worst to go up. We leave more complicated and directional
distance constraints for future studies.

##  6 Conclusion

We show that the current practice of applying pre-trained models to the
personalized dialogue generation task is volatile across different input
orders of personas. Through the analysis, we find that the problem arises from
the representation changes induced by the input changes. Motivated by these,
we propose our ORIG, a model-agnostic framework for finetuning the persona
dialogue model such that it obtains a persona order-invariant representation.
Experiments on two dominant pre-trained dialogue models show that our
framework improves performance and reduces order volatility.

## Limitations

In this section, we discuss the limitations of this work. First, on the
problems side, it’s non-trivial to consider the order of all kinds of
grounding knowledge, but we have only explored Persona-Chat. We hope to apply
our method to more grounded generation tasks such as knowledge-grounded and
document-grounded dialogue in the future. Second, on the methods side, our
framework is training-based, but we hope more lightweight techniques could be
developed to improve the model’s robustness even without training the model.

## Acknowledgements

We would like to thank Professor Helen Meng and Xixin Wu for their helpful
discussion and feedback on the course SEEM5640. We also thank anonymous
reviewers for their constructive comments. Thanks to Dr Honshan HO for his
support. This research work is partially supported by CUHK under Project No.
3230366.

## References

  * Cao et al. (2022) Yu Cao, Wei Bi, Meng Fang, Shuming Shi, and Dacheng Tao. 2022.  A model-agnostic data manipulation method for persona-based dialogue generation.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 7984–8002, Dublin, Ireland. Association for Computational Linguistics.
  * Chen (2020) Liang Chen. 2020.  Variance-reduced language pretraining via a mask proposal network.  _CoRR_ , abs/2008.05333.
  * Deng et al. (2022a) Yang Deng, Yaliang Li, Wenxuan Zhang, Bolin Ding, and Wai Lam. 2022a.  Toward personalized answer generation in e-commerce via multi-perspective preference modeling.  _ACM Trans. Inf. Syst._ , 40(4):87:1–87:28.
  * Deng et al. (2022b) Yang Deng, Wenxuan Zhang, Wai Lam, Hong Cheng, and Helen Meng. 2022b.  User satisfaction estimation with sequential dialogue act modeling in goal-oriented conversational systems.  In _WWW ’22: The ACM Web Conference 2022_ , pages 2998–3008.
  * Deng et al. (2022c) Yang Deng, Wenxuan Zhang, Weiwen Xu, Wenqiang Lei, Tat-Seng Chua, and Wai Lam. 2022c.  A unified multi-task learning framework for multi-goal conversational recommender systems.  _CoRR_ , abs/2204.06923.
  * Deng et al. (2023) Yang Deng, Wenxuan Zhang, Yifei Yuan, and Wai Lam. 2023.  Knowledge-enhanced mixed-initiative dialogue system for emotional support conversations.  _arXiv preprint arXiv:2305.10172_.
  * Devlin et al. (2018) Jacob Devlin, Ming-Wei Chang, Kenton Lee, and Kristina Toutanova. 2018.  Bert: Pre-training of deep bidirectional transformers for language understanding.  _arXiv preprint arXiv:1810.04805_.
  * Fleiss (1971) Joseph L Fleiss. 1971.  Measuring nominal scale agreement among many raters.  _Psychological bulletin_ , 76(5):378.
  * Gu et al. (2019) Jia-Chen Gu, Zhen-Hua Ling, Xiaodan Zhu, and Quan Liu. 2019.  Dually interactive matching network for personalized response selection in retrieval-based chatbots.  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 1845–1854, Hong Kong, China. Association for Computational Linguistics.
  * Ham et al. (2020) Donghoon Ham, Jeong-Gwan Lee, Youngsoo Jang, and Kee-Eung Kim. 2020.  End-to-end neural pipeline for goal-oriented dialogue systems using GPT-2.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 583–592, Online. Association for Computational Linguistics.
  * Holtzman et al. (2020) Ari Holtzman, Jan Buys, Li Du, Maxwell Forbes, and Yejin Choi. 2020.  The curious case of neural text degeneration.
  * Huang et al. (2020) Minlie Huang, Xiaoyan Zhu, and Jianfeng Gao. 2020.  Challenges in building intelligent open-domain dialog systems.  _ACM Transactions on Information Systems (TOIS)_ , 38(3):1–32.
  * Kingma and Ba (2015) Diederik P Kingma and Jimmy Ba. 2015.  Adam: A method for stochastic optimization.  In _ICLR_.
  * Kulhánek et al. (2021) Jonáš Kulhánek, Vojtěch Hudeček, Tomáš Nekvinda, and Ondřej Dušek. 2021.  AuGPT: Auxiliary tasks and data augmentation for end-to-end dialogue with pre-trained language models.  In _Proceedings of the 3rd Workshop on Natural Language Processing for Conversational AI_ , pages 198–210, Online. Association for Computational Linguistics.
  * Lewis et al. (2020) Mike Lewis, Yinhan Liu, Naman Goyal, Marjan Ghazvininejad, Abdelrahman Mohamed, Omer Levy, Veselin Stoyanov, and Luke Zettlemoyer. 2020.  BART: Denoising sequence-to-sequence pre-training for natural language generation, translation, and comprehension.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 7871–7880, Online. Association for Computational Linguistics.
  * Lin (2004) Chin-Yew Lin. 2004.  ROUGE: A package for automatic evaluation of summaries.  In _Text Summarization Branches Out_ , pages 74–81, Barcelona, Spain. Association for Computational Linguistics.
  * Liu et al. (2022) Yifan Liu, Wei Wei, Jiayi Liu, Xianling Mao, Rui Fang, and Dangyang Chen. 2022.  Improving Personality Consistency in Conversation by Persona Extending.  In _Proceedings of the 31st ACM International Conference on Information & Knowledge Management_, pages 1350–1359.
  * Liu et al. (2019) Yinhan Liu, Myle Ott, Naman Goyal, Jingfei Du, Mandar Joshi, Danqi Chen, Omer Levy, Mike Lewis, Luke Zettlemoyer, and Veselin Stoyanov. 2019.  Roberta: A robustly optimized bert pretraining approach.  _arXiv preprint arXiv:1907.11692_.
  * Lu et al. (2022) Yao Lu, Max Bartolo, Alastair Moore, Sebastian Riedel, and Pontus Stenetorp. 2022\.  Fantastically ordered prompts and where to find them: Overcoming few-shot prompt order sensitivity.  In _Proceedings of the 60th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 8086–8098, Dublin, Ireland. Association for Computational Linguistics.
  * Madotto et al. (2019) Andrea Madotto, Zhaojiang Lin, Chien-Sheng Wu, and Pascale Fung. 2019.  Personalizing dialogue agents via meta-learning.  In _Proceedings of ACL 2019_ , pages 5454–5459.
  * Papineni et al. (2002) Kishore Papineni, Salim Roukos, Todd Ward, and Wei-Jing Zhu. 2002.  Bleu: a method for automatic evaluation of machine translation.  In _Proceedings of the 40th Annual Meeting of the Association for Computational Linguistics_ , pages 311–318, Philadelphia, Pennsylvania, USA. Association for Computational Linguistics.
  * Radford et al. (2019) Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. 2019.  Language models are unsupervised multitask learners.  _OpenAI blog_ , 1(8):9.
  * Song et al. (2021) Haoyu Song, Yan Wang, Kaiyan Zhang, Wei-Nan Zhang, and Ting Liu. 2021.  BoB: BERT over BERT for training persona-based dialogue models from limited personalized data.  In _Proceedings of the 59th Annual Meeting of the Association for Computational Linguistics and the 11th International Joint Conference on Natural Language Processing (Volume 1: Long Papers)_ , pages 167–177, Online. Association for Computational Linguistics.
  * Song et al. (2020a) Haoyu Song, Yan Wang, Weinan Zhang, Xiaojiang Liu, and Ting Liu. 2020a.  Generate, delete and rewrite: A three-stage framework for improving persona consistency of dialogue generation.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , pages 5821–5831.
  * Song et al. (2019) Haoyu Song, Wei-Nan Zhang, Yiming Cui, Dong Wang, and Ting Liu. 2019.  Exploiting Persona Information for Diverse Generation of Conversational Responses.  In _Proceedings of the Twenty-Eighth International Joint Conference on Artificial Intelligence_ , pages 5190–5196, Macao, China. International Joint Conferences on Artificial Intelligence Organization.
  * Song et al. (2020b) Haoyu Song, Wei-Nan Zhang, Jingwen Hu, and Ting Liu. 2020b.  Generating Persona Consistent Dialogues by Exploiting Natural Language Inference.  _Proceedings of the AAAI Conference on Artificial Intelligence_ , 34(05):8878–8885.
  * Vaswani et al. (2017) Ashish Vaswani, Noam Shazeer, Niki Parmar, Jakob Uszkoreit, Llion Jones, Aidan N Gomez, Ł ukasz Kaiser, and Illia Polosukhin. 2017.  Attention is all you need.  In _Advances in Neural Information Processing Systems_ , volume 30. Curran Associates, Inc.
  * Vedantam et al. (2015) R. Vedantam, C. Zitnick, and D. Parikh. 2015.  Cider: Consensus-based image description evaluation.  In _CVPR_ , pages 4566–4575, Los Alamitos, CA, USA. IEEE Computer Society.
  * Wolf et al. (2020) Thomas Wolf, Lysandre Debut, Victor Sanh, Julien Chaumond, Clement Delangue, Anthony Moi, Pierric Cistac, Tim Rault, Rémi Louf, Morgan Funtowicz, Joe Davison, Sam Shleifer, Patrick von Platen, Clara Ma, Yacine Jernite, Julien Plu, Canwen Xu, Teven Le Scao, Sylvain Gugger, Mariama Drame, Quentin Lhoest, and Alexander M. Rush. 2020.  Transformers: State-of-the-art natural language processing.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing: System Demonstrations_ , pages 38–45, Online. Association for Computational Linguistics.
  * Wolf et al. (2019) Thomas Wolf, Victor Sanh, Julien Chaumond, and Clement Delangue. 2019.  TransferTransfo: A Transfer Learning Approach for Neural Network Based Conversational Agents.  _arXiv:1901.08149 [cs]_.
  * Wu et al. (2020a) Bowen Wu, Mengyuan Li, Zongsheng Wang, Yifu Chen, Derek F. Wong, Qihang Feng, Junhong Huang, and Baoxun Wang. 2020a.  Guiding variational response generator to exploit persona.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics, ACL 2020, Online, July 5-10, 2020_ , pages 53–65.
  * Wu et al. (2021) Chen Henry Wu, Yinhe Zheng, Xiaoxi Mao, and Minlie Huang. 2021.  Transferable persona-grounded dialogues via grounded minimal edits.  In _Proceedings of the 2021 Conference on Empirical Methods in Natural Language Processing_ , pages 2368–2382, Online and Punta Cana, Dominican Republic. Association for Computational Linguistics.
  * Wu et al. (2020b) Chien-Sheng Wu, Steven C.H. Hoi, Richard Socher, and Caiming Xiong. 2020b.  TOD-BERT: Pre-trained natural language understanding for task-oriented dialogue.  In _Proceedings of the 2020 Conference on Empirical Methods in Natural Language Processing (EMNLP)_ , pages 917–929, Online. Association for Computational Linguistics.
  * Zhang et al. (2018a) Saizheng Zhang, Emily Dinan, Jack Urbanek, Arthur Szlam, Douwe Kiela, and Jason Weston. 2018a.  Personalizing Dialogue Agents: I have a dog, do you have pets too? In _Proceedings of the 56th Annual Meeting of the Association for Computational Linguistics (Volume 1: Long Papers)_ , pages 2204–2213, Melbourne, Australia. Association for Computational Linguistics.
  * Zhang et al. (2018b) Yizhe Zhang, Michel Galley, Jianfeng Gao, Zhe Gan, Xiujun Li, Chris Brockett, and Bill Dolan. 2018b.  Generating informative and diverse conversational responses via adversarial information maximization.  In _NIPS 2018_ , pages 1810–1820.
  * Zhao et al. (2021) Zihao Zhao, Eric Wallace, Shi Feng, Dan Klein, and Sameer Singh. 2021.  Calibrate before use: Improving few-shot performance of language models.  In _International Conference on Machine Learning_ , pages 12697–12706. PMLR.