# Data-driven Abstractions with Probabilistic Guarantees for Linear PETC
Systems

Andrea Peruffo and Manuel Mazo Jr This work was supported by the European
Research Council through the SENTIENT project (ERC-2017-STG #755953).A.
Peruffo and M. Mazo are with Faculty of Mechanical, Maritime and Materials
Engineering, TU Delft, Delft, The Netherlands<EMAIL_ADDRESS>
###### Abstract

We employ the scenario approach to compute probably approximately correct
(PAC) bounds on the average inter-sample time (AIST) generated by an unknown
PETC system, based on a finite number of samples. We extend the scenario
approach to multiclass SVM algorithms in order to construct a PAC map between
the concrete, unknown state-space and the inter-sample times. We then build a
traffic model applying an $\ell$-complete relation and find, in the underlying
graph, the cycles of minimum and maximum average weight: these provide lower
and upper bounds on the AIST. Numerical benchmarks show the practical
applicability of our method, which is compared against model-based state-of-
the-art tools.

##  I INTRODUCTION

In the last decades, thanks to the increasing digitalisation and use of
communication networks, control systems have faced several new challenges.
Arguably, the most compelling task is ensuring the stability of an
interconnection between an analog plant and a digital controller, possibly in
spite of imperfect communication means. The interface between a (digital)
controller and an (analog) plant is typically implemented with a periodic
sampling of the plant, whose measurements are transmitted to the controller,
which computes the actions in order to optimise a performance cost. The
sampling period itself represents a tradeoff between performance and energy
consumption – any control signal entails an action by the actuator, besides
potentially congesting the communication network.

Event-triggered control (ETC) is a paradigm that tackles this issue, adjusting
the sampling according to the satisfaction of a condition, whilst maintaining
the stability guarantees. This notion has originally been developed in [1],
and further notably developed in [2] where guarantees on the closed loop
performance are ensured. A practical implementation procedure of this scheme
is the periodic ETC (PETC), where a stability condition is periodically
checked whilst the measurement is transmitted solely when the condition is
verified. Whilst the advantage of this approach is apparent, formally and
quantitatively _measuring_ its performance has been tackled only recently.

The use of formal abstractions for PETC models has been preparatory in this
sense, see e.g. [3, 4]. More recently, the work [5] provides a
characterisation in terms of traffic abstractions: a finite-state automaton
considering the inter-sample times (ISTs) sequences of a PETC system. The
procedure is applied in [6], shifting the focus to $\ell$ consecutive inter-
sample times: this offers a conservative estimate of the long-term performance
of a PETC system. Further, in [7] the authors build a traffic abstraction in
order to compute the minimum average inter-sample time (AIST) of a PETC
system, a metric that can be translated directly to the expected network load
or resource utilization. ETCetera, a state-of-the-art tool to compute the
sampling performance of ETC systems is presented in [8].

We build upon this literature, aiming at constructing finite-state abstraction
of a PETC system, with a crucial difference. In this work, we do not require
any knowledge about the underlying concrete system. Nevertheless, we construct
a data-driven map between the concrete state-space and the inter-sample times
with probably approximately correct (PAC) guarantees, which acts as the
foundation for a traffic abstraction to compute reliable bounds on the AIST of
the unknown system. Data-driven abstractions have recently gained interest: in
[9, 10] the authors provide a sampled-based interval MDP, employing the
scenario approach to provide bounds on the transition probabilities, whilst
the state space is partitioned with a gridding procedure.

Since the concrete model is unknown, building the relationship between the
state-space and the corresponding ISTs is a non-trivial challenge. We provide
a map based on a finite number of samples (often called scenarios) which we
assume can be computed via simulations. We adapt the scenario approach which
provides probabilistic guarantees by solving a convex optimisation program
[11, 12, 13, 14]. We use this map to partition the state space of the concrete
system. Each partition corresponds to an abstract state of the traffic model,
whose transitions are governed by the so-called domino rule. We then
extrapolate upper and lower bounds on the AIST; by increasing $\ell$, the
procedure can be refined until the upper and lower bounds reach a desired
precision. The bounds are PAC, as the true AIST value is contained within
these boundaries with a probability not less than a user-designed confidence
level.

Contributions In this work, we elaborate an extension to [14] as we tailor the
scenario approach to multiclass SVM algorithms. We employ this result to build
a data-driven abstraction of an unknown PETC system with probabilistic
guarantees of correctness. We aim at estimating their resource consumption by
identifying the possible (infinite) sequences of inter-sample times. To this
end, we provide probably correct bounds that tightly approximate the desired
consumption cost. Finally, we compare our procedure against the model-based
tool ETCetera [8].

##  II Finite Abstraction of PETC via TS

Consider a linear time-invariant plant controlled with sample-and-hold state
feedback described by

$\dot{\xi}(t)=A\xi(t)+B\nu(t),\quad\nu(t)=K\hat{\xi}(t),$ (1)

where $\xi(t)\in\mathbb{R}^{n_{x}}$ is the plant’s state with initial value
$x_{0}:=\xi(0)$, $\hat{\xi}(t)\in\mathbb{R}^{n_{x}}$ is the state measurement
available to the controller, $\nu(t)\in\mathbb{R}^{n_{u}}$ is the control
input, $n_{x}$ and $n_{u}$ are the state-space and input-space dimensions,
respectively, and $A$, $B$, $K$ are matrices of appropriate dimensions. The
measurements are updated to the controller only at specific sampling times,
with their values being zero-order held on the controller: let
$t_{i}\in\mathbb{R}_{+}$, $i\in\mathbb{N}_{0}$ be a sequence of sampling
times, with $t_{0}=0$ and $t_{i+1}-t_{i}>\varepsilon$ for some
$\varepsilon>0$; then $\xi(t)=\xi(t_{i})$, $\forall\,t\in[t_{i},t_{i+1})$. In
ETC, a triggering condition determines the sequence of times $t_{i}$. In the
case of PETC, this condition is checked only periodically, with a fundamental
checking period $h$.

We typically consider the family of quadratic triggering conditions [15] where
we additionally set a maximum inter-sampling time $\overline{\kappa}$, known
as the heartbeat of the system. Formally, we define the $(i+1)$-th triggering
time as

$t_{i+1}=\\\ \inf\left\\{kh>t_{i}\ \left|\ \begin{aligned}
&\begin{bmatrix}\xi(kh)\\\
\xi(t_{i})\end{bmatrix}^{T}R\begin{bmatrix}\xi(kh)\\\
\xi(t_{i})\end{bmatrix}>0\\\ &\text{ or }kh-
t_{i}\geq\overline{\kappa}\end{aligned}\right.\right\\},$ (2)

where $k\in\mathbb{N}$ and $R\in\mathbb{S}^{2n_{x}}$ is the designed
triggering matrix, and $\overline{\kappa}$ is the chosen maximum inter-sample
time. Every run of system (1), starting from initial condition $\xi(0)$,
generates an infinite sequence of samples $\\{\xi(t_{i})\\}$ and of inter-
sample times $\\{\tau_{i}\\}$. In the following, we solely consider PETC
settings hence $\tau\in h\cdot\\{1,2,\ldots\overline{\kappa}\\}$; for
simplicity and without loss of generality, we consider $h=1$.

A typical metric of interest is the average inter-sample time (AIST), defined
for every initial state $\xi(0)$ as

$\text{AIST}(\xi(0))=\liminf\limits_{n\rightarrow\infty}\frac{1}{n+1}\sum_{i=0}^{n}\tau(\xi(t_{i})).$
(3)

Notice that we use the liminf instead of lim in case the regular limit does
not exist [16], making the AIST a well-defined metric. Additionally we define
the smallest and the largest average inter-sample time (SAIST and LAIST,
respectively) as

$\text{SAIST}:=\inf_{\xi\in\mathbb{R}^{n_{x}}}\liminf\limits_{n\rightarrow\infty}\frac{1}{n+1}\sum_{i=0}^{n}\tau(\xi(t_{i})),$
(4)
$\text{LAIST}:=\sup_{\xi\in\mathbb{R}^{n_{x}}}\limsup\limits_{n\rightarrow\infty}\frac{1}{n+1}\sum_{i=0}^{n}\tau(\xi(t_{i})).$
(5)

Both the SAIST and the LAIST are crucial metrics to assess the performance (in
terms of resources consumption or band utilisation) of an ETC implementation.
However, the present expressions (4), (5) require the search for a state $\xi$
over $\mathbb{R}^{n_{x}}$ and the choice of a sufficiently large $n$, which
are tasks computationally hard (if at all possible). To overcome this
impediment, we approach this problem exploiting the (finite-state)
abstractions theory.

###  II-A Abstractions and Transition Systems

The abstraction of a system allows the analysis of large (even infinite)
models. We usually consider a concrete model, which is treated as a ground
truth; this is transformed, simplified, and adapted to accommodate the
analysis of its behavior. Several kinds of abstractions are available for
different purposes: we employ a finite-state abstraction in the form of a
(weighted) transition system (WTS).

######  Definition 1 (Weighted Transition System (adapted from [4, 17]))

A transition system $\mathcal{S}$ is a tuple
$(\mathcal{X},\mathcal{X}_{0},\mathcal{E},\mathcal{Y},\mathcal{H},\gamma)$
where:

  * •

$\mathcal{X}$ is the set of states,

  * •

$\mathcal{X}_{0}\subseteq\mathcal{X}$ is the set of initial states,

  * •

$\mathcal{E}\subseteq\mathcal{X}\times\mathcal{X}$ is the set of edges, or
transitions,

  * •

$\mathcal{Y}$ is the set of outputs, and

  * •

$\mathcal{H}:\mathcal{X}\rightarrow\mathcal{Y}$ is the output map,

  * •

$\gamma$ : $\mathcal{E}\rightarrow\mathbb{Q}$ is the weight function.

The original definition also includes the action set $\mathcal{U}$ which is
here omitted since we solely consider autonomous systems; we further consider
finite-state systems, where the cardinality of $\mathcal{X}$ is finite. We
tacitly consider non-blocking transition systems, i.e. automata where every
state is equipped with at least one outgoing transition.

Let us define $r=x_{0}x_{1}x_{2}\ldots$ an infinite internal behavior, or run
of $\mathcal{S}$ if $x_{0}\in\mathcal{X}_{0}$ and
$(x_{i},x_{i+1})\in\mathcal{E}$ for all $i\in\mathbb{N}$, and, with slight
abuse of notation, $\mathcal{H}(r)=y_{0}y_{1}y_{2}\ldots$ its corresponding
external behavior, or trace, if $\mathcal{H}(x_{i})=y_{i}$ for all
$i\in\mathbb{N}$. Similarly, we define $\gamma(r)=v_{0}v_{1}\ldots$ the
sequence of weights from run $r$, where $\gamma(x_{i},x_{i+1})=v_{i}$. Let us
further consider a value function, i.e. a function mapping an infinite
sequence of weights to a (possibly finite) value, as

$\operatorname{LimAvg}(\gamma(r)):=\liminf\limits_{n\rightarrow\infty}\frac{1}{n+1}\sum_{i=0}^{n}v_{i}.$
(6)

A weighted automaton equipped with the LimAvg value function is called a
LimAvg-automaton [17].

Closely related to this metric, we can define

$\displaystyle\overline{V}(\mathcal{S}):=\sup\\{\operatorname{LimAvg}(\gamma(r))\mid
r\text{ is a run of }\mathcal{S}\\},$ (7)
$\displaystyle\underline{V}(\mathcal{S}):=\inf\\{\operatorname{LimAvg}(\gamma(r))\mid
r\text{ is a run of }\mathcal{S}\\}.$ (8)

Remarkably, [17, 18] show that we can recover from a WTS the value of
$\underline{V}(\mathcal{S})$ and $\overline{V}(\mathcal{S})$ in polynomial
time. The value function in (7) evaluates to the smallest average cycle (SAC)
of the graph underlying the transition system. In many contexts, the
performance of systems as the (minimum) average resource consumption is
modeled as the minimum cycle mean problem. Analogously, we may be interested
in the largest average cycle (LAC) to analyse the maximum average resource
consumption.

We ideally would abstract a PETC system as a WTS. However, the abstraction
requires the knowledge on the internal behaviour of the system, i.e. the
states $\xi$ and their dynamics. We then introduce the notion of _behavioural
inclusion_ : the abstraction is oblivious to the internal behaviour of a
system, but we require that all traces observed in the concrete system are
also observed in the abstraction. In practical terms, the ISTs of any
trajectory of the concrete PETC system must overlap the output of a run of the
weighted TS.

A natural way of building a behavioural inclusion abstraction is by mapping
each possible output symbol $\tau_{i}$ to an abstract state $x_{i}$. We may
elaborate this intuition through a so-called $\ell$-complete model:

######  Definition 2 ((Strongest) $\ell$-complete abstraction [7])

Let
$\mathcal{S}:=(\mathcal{X},\mathcal{X}_{0},\mathcal{E},\mathcal{Y},\mathcal{H})$
be a transition system, and let
$\mathcal{X}_{\ell}\subseteq\mathcal{Y}_{\ell}$ be the set of all $\ell$-long
subsequences of all behaviors in $\mathcal{S}$. Then, the system
$\mathcal{S}_{\ell}=(\mathcal{X}_{\ell},B_{\ell}(\mathcal{S}),\mathcal{E}_{\ell},\mathcal{Y},\mathcal{H})$
is called the (strongest) $\ell$-complete abstraction (S$\ell$-CA) of
$\mathcal{S}$, where

  * •

$\mathcal{E}_{l}$ = $\\{(k\sigma,\sigma
k^{\prime})\,|\,k,k^{\prime}\in\mathcal{Y}$, $\sigma\in\mathcal{Y}_{\ell-1}$,
$k\sigma$, $\sigma k^{\prime}$ $\in\mathcal{X}_{\ell}$ },

  * •

$\mathcal{H}(k\sigma)=k$,

where we denote $B_{\ell}(\mathcal{S})$ all the possible (infinite) external
traces of system $\mathcal{S}$. The intuition behind the S$\ell$-CA is to
encode each state as an $\ell$-long external trace. Notice that the
transitions follow the so-called “domino rule”: e.g., let us assume $\ell=3$
and let us observe a trace abc (this trace corresponds to a single abstract
state); the next $\ell$-trace must begin with bc. Therefore, a transition from
abc can lead to e.g. bca, bcb, bcc. Finally, the output of a state is its
first element: state abc has output $\mathcal{H}(abc)=a$.

$\\{1\\}$$\\{2\\}$$\\{1,1\\}$$\\{1,2\\}$$\\{2,2\\}$$\\{1,1,2\\}$$\\{1,2,2\\}$$\\{2,2,2\\}$$\\{1,1,1\\}$
Figure 1: S$\ell$-CA with $\tau_{i}=\\{1,2\\}$ and $\ell$=1 (left), $\ell=2$
(center), $\ell=3$ (right).

The S$\ell$-CA translation is particularly useful when little or no
information is available about the concrete system, as only the external
behaviour, i.e. the sequences of $\tau_{i}$, is employed to build the
abstraction. In order to compute the AIST, which is a function of $\xi(0)$, we
shall need a map, denoted $\mathcal{T}:\xi\rightarrow\tau$, that relates
concrete states to inter-sample times in order to compute the initial abstract
state $x_{0}$. Further, the S$\ell$-CA is in general non-deterministic: we
cannot evaluate exactly the LimAvg (as every run starting from $x_{0}$
branches into several possible runs), thus we compute the SAC and LAC (see
(7)) and use them as upper and lower approximations of the LimAvg, i.e. the
AIST. Figure 1 shows three examples of S$\ell$-CA, where $\tau_{i}=\\{1,2\\}$
and $\ell=1,2,3$. Considering $\ell=3$ and as initial state
$x_{0}=\\{1,1,1\\}$, we notice that its SAC and LAC are the self-loop on
states $(1,1,1)$ and $(2,2,2)$ respectively. Therefore, the AIST is within
$[1,2]$.

The triggering condition (see (2)) allows solely a _subset_ of all possible
$\ell$-sequences of ISTs. A model-based method can exploit the knowledge of
the concrete system to check which sequences of length $\ell$ are admissible
and construct a tailored TS.

In the following, we employ a scenario approach to obtain the map
$\mathcal{T}$ with guarantees of correctness and carefully tailor the abstract
state space without any knowledge of the underlying concrete system.

##  III Data-driven Abstractions with Guarantees

Naturally, full knowledge of the concrete system is useful to compute the
mapping $\mathcal{T}$ between the states $\\{\xi(t_{i})\\}$ and the output
traces $\\{\tau_{i}\\}$. However, in many applications this knowledge may be
unavailable, unreliable, or simply expensive to obtain. To overcome this
impediment, we employ the scenario approach [11].

Let us assume we collect $N$ samples $Q_{i}=(\mathbf{X}_{i},\mathbf{Y}_{i})$,
$i=1,\dots N$, where $\mathbf{X}_{i}$ represents the $i$-th sample of the
concrete system state and $\mathbf{Y}_{i}$ represents an $\ell$-sequence of
ISTs. Since $\mathbf{Y}_{i}$ have finite cardinality, we may associate them
with classes or _labels_ from a machine learning viewpoint. From now on, we
consider $\\{\mathbf{Y}_{i}\\}$ belonging to $L$ different classes, i.e.
$\mathbf{Y}_{i}\in\\{1,\dots L\\}$.

For PETC systems, the regions of the state space that correspond to
$\ell$-sequences of ISTs have a well-defined shape, as they are unions of
cones [5, 6, 7], as depicted in Fig. 2. We shall then use this intuition to
partition the state space and construct the abstract states. This allows to
reduce the number of abstracted states in comparison to an agnostic gridding
procedure.

Figure 2: IST regions are unions of (diametrically opposite) cones: black
lines denote the regions’ boundaries, depicted along with 1000 samples in
different colors, for $\ell=2$.

###  III-A Linear Separability with Veronese Embedding

We draw inspiration from the SVM literature, where hyper-planes are
constructed in order to split linearly separable datasets. Typically, when the
samples are not linearly separable, we employ the kernel trick [19] to embed
the data into a higher-dimensional space, where a linear separation is
possible. A model given by (1)-(2) separates the state space into (union of)
cones: hence, a conic transformation to the samples $\mathbf{X}_{i}$ grants a
linearly separable dataset. This embedding is known as the Veronese map [20]
of order 2 ,
$\mathcal{V}_{2}:\mathbb{R}^{n}\rightarrow\mathbb{R}^{\frac{n(n+1)}{2}}$,
defined by

$\mathcal{V}_{2}(x):=[x_{1}^{2}\ x_{1}x_{2}\ x_{2}^{2}\ \ldots\ x_{n}^{2}],$
(9)

where $x_{j}$ indicates the $j$-th component of vector $x$. This embedding
represents a tailored kernel trick for the problem at hand. Further, the conic
partitions fulfil an _encapsulation_ constraint: every point of the concrete
system $\xi$ whose next IST is $j$ satisfies

$\xi^{T}N_{i}\xi<0\text{ for }i<j,\quad\xi^{T}N_{j}\xi>0,$ (10)

where the set of matrices $N_{i}$ is a function of $A$, $B$, $K$ and $R$ (see
(1)-(2)). Intuitively, the $N_{i}$ indicate a violation of the $i$-th
triggering condition. For instance, if $\xi^{T}N_{1}\xi<0$, the triggering
condition is not violated after 1 inter-sample times; conversely, if
$\xi^{T}N_{2}\xi>0$ the triggering condition is violated after 2 ISTs,
provided that it is not violated after 1 IST (i.e. $\xi^{T}N_{1}\xi<0$ must
hold).

We map conditions (10) with the Veronese embedding and obtain a set of linear
constraints

$W_{i}\cdot\mathcal{V}_{2}(\xi)<0\text{ for }i<j,\quad
W_{j}\cdot\mathcal{V}_{2}(\xi)>0,$ (11)

where $W_{i}$ shall be recovered from the samples $Q_{i}$. Constraints (11)
closely resemble a multiclass SVM approach. In the following, we outline the
scenario theory for a (more general) SVM multiclass problem, highlighting the
adjustments needed to fit the encapsulation problem (11).

###  III-B Sample-based Partitioning via Classification

Building upon [14], where binary SVM with scenario guarantees is presented, we
extend this approach to multiclass SVM algorithms. This procedure provides a
classifier with guarantees of correctness, which we denote as the map
$\mathcal{T}$. Two methodologies exist to achieve multiclass classification
[21]: the _one-vs-one_ reduction, where the multi-class problem is split into
multiple binary classification problems, and the _one-vs-all_ approach, which
defines one hyperplane per class. Notably, the one-vs-all approach can be
written in one single optimisation program: for clarity, we select the
Crammer-Singer formulation [22]. The extension to one-vs-one and other one-vs-
all formulation proceeds similarly to the following discussion, and is omitted
here for brevity.

The one-vs-all SVM algorithm consists of one convex problem considering $L$
(one per class) hyperplanes, defined

$f_{j}(\mathbf{X}_{i}):=W_{j}\mathbf{X}_{i}+b_{j},\text{ for
}j\in\\{1,\dots,L\\},$ (12)

where $W_{j}$ $\in\mathbb{R}^{n\times 1}$, $b_{j}\in\mathbb{R}$,
$\forall\,j\in\\{1,\ldots L\\}$. The classification decision follows the
winner-takes-all policy; formally

$D(\mathbf{X}_{i}):=\arg\max\\{W_{j}\mathbf{X}_{i}+b_{j}\\}.$ (13)

For every sample $\mathbf{X}_{i}$, the corresponding hyperplane is denoted as
$(W_{y_{i}},b_{y_{i}})$, i.e. the $\mathbf{Y}_{i}$-th hyperplane. For a
correct classification, the value of hyperplane
$W_{y_{i}}\mathbf{X}_{i}+b_{y_{i}}$ ought to be greater than all others: we
may rewrite (13) as

$\zeta-(W_{y_{i}}-W_{j})\mathbf{X}_{i}+(b_{y_{i}}-b_{j})\leq 0,\quad\forall
j\neq\mathbf{Y}_{i},\ \forall\,i.$ (14)

where the hyper-parameter $\zeta>0$ is added for numerical stability.
Conditions (14) can be simplified as

$g(\mathbf{X}_{i}):=\max_{j\neq
y_{i}}\\{\zeta-(W_{y_{i}}-W_{j})\mathbf{X}_{i}-(b_{y_{i}}-b_{j})\\}.$ (15)

Constraints $g(\mathbf{X}_{i})\leq 0$ can be satisfied only if the dataset is
linearly separable: to further accommodate for more general cases, we employ
slack variables $\theta_{i}\geq 0$, $i=1,\ldots,N$, impose
$g(\mathbf{X}_{i})\leq\theta_{i}$ and minimise the sum of $\theta_{i}$. The
multi-class SVM problem expression follows standard formulation [19]. An
$L$-class classifier can be obtained by solving the following convex program:

$\displaystyle\min_{W,b,\theta_{i}\geq 0}$
$\displaystyle\sum^{L}_{i=1}||W_{i}||^{2}+\rho\sum_{i=1}^{N}\theta_{i},$ (16)
s.t. $\displaystyle g(\mathbf{X}_{i})\leq\theta_{i},\quad\,i=1,\ldots,N,$

where $\rho>0$ is a hyper-parameter balancing the trade-off between the
correctness of the algorithm (the number of positive $\theta_{i}$) and its
cost (the norm of matrices $W_{j}$).

Let us now introduce a quantitative measure to evaluate the reliability of the
classifier. We present the concept of risk (or violation probability), which
is a measure of the probability that a (new, unseen) sample is misclassified
[14].

###### Definition 3

The probability (risk) of violating a constraint
$f(\mathbf{X}_{j},\mathbf{Y}_{j})$, $j>N$, is denoted

$R(\mathbf{S}):=\mathbb{P}[(\mathbf{X}_{j},\mathbf{Y}_{j}):g(\mathbf{X}_{j})>0\,],$
(17)

where $f(\mathbf{X}_{j})$ is defined according to Eq. (15) and where we denote
as $\mathbf{S}$ the parameters of the SVM algorithm ($W_{j}$, $b_{j}$) for all
$j=1,\ldots L$.

We can provide a quantitative evaluation of the risk within the optimisation
context of program (16): we mimic the discussion in [14] for binary SVM and
adapt it to a multiclass environment.

######  Theorem 1 (Adapted from [14])

Given a confidence parameter $\beta\in[0,1]$ and $N$ samples, it holds that

$\mathbb{P}^{N}[\underline{\epsilon}(s^{*},N,\beta)\leq
R(\mathbf{S}^{*})\leq\overline{\epsilon}(s^{*},N,\beta)]>1-3\beta,$ (18)

where $\mathbf{S}^{*}$ represents the parameters that minimise program (16)
and $s^{*}$ identifies the number of violated constraints, i.e. the number of
samples that return $g(\mathbf{X}_{i})>0$. Further, the event of
misclassification can be bounded by

$\mathbb{P}^{N}[\mathbb{P}[\text{misclassification}]\leq\overline{\epsilon}(s^{*},N,\beta)]>1-3\beta.$
(19)

The bounds $\underline{\epsilon}$, $\overline{\epsilon}$ can be found solving
a polynomial equation, function of $s^{*}$, $N$, $\beta$, as outlined in [14].

The proof follows a similar result in [14] and is omitted for brevity.

#### Remark

It is worth highlighting that in program (16) the violation of a constraint
does not imply misclassification: it reports that the evaluation of two
hyperplanes differs less than $\zeta$. As such, misclassification occurs more
rarely than constraints violation. Therefore, Theorem 1 can solely provide an
upper bound on the probability of misclassification. Notice that $\beta$ is a
tunable parameter, which ensures desired performance of the algorithm, since
$\overline{\epsilon}$ is a function of $s^{*}$, $\beta$ and $N$. $\square$

The hyperplanes defined by the classification algorithm outline the state-
space partitions, and each partition corresponds to an abstract state of the
$\ell$-complete model. Given an initial state $\xi(0)$, we employ the
classifier to map it to its corresponding abstract state, say $x_{0}$. We then
evaluate the SAC and LAC that are reachable from $x_{0}$ in order to give
upper and lower bounds for the AIST($\xi(0)$).

#### Remark

Conditions (11) can be fitted in program (16) by changing the classification
decision (13) to reflect that the _first_ violation of the conic constraints
defines the class appointment. Formally,

$D(\mathbf{X}_{i}):=\arg\min\\{W_{j}\cdot\mathcal{V}_{2}(\mathbf{X}_{i})>0\\},$
(20)

so that conditions (14) shall be replaced by (11). We refer to this procedure
as conic multiclass SVM (CM-SVM). $\square$

###  III-C AIST Evaluation with Guarantees

The map $\mathcal{T}$, thanks to the scenario theory, is equipped with
probabilistic guarantees of correctness, which are delivered to the partitions
of the concrete state space and thus to the abstract states of the S$\ell$-CA.
Its transitions, on the other hand, are correct by design following the domino
rule, albeit they might introduce spurious behaviours.

The state space of the $\ell$-complete model raises a question. Assume
$\ell=2$, $\tau_{i}=\\{1,2\\}$, and our dataset presents the 2-sequences
$\\{(1,1),(1,2),(2,2)\\}$ but not $(2,1)$. We can gather a larger dataset
until we observe the missing sequence; however, this might never happen as
this particular 2-sequence may not be allowed by the triggering condition.

We synthesise a classifier based upon the dataset at hand: any new sample with
an unseen label (not amongst the $L$ labels witnessed within the sample set)
is evidently misclassified. We can thus rethink the misclassification of
Theorem 1 as entailing both a mis-labeling, i.e. the algorithm assigns a wrong
label to a sample, and a new labeling, i.e. a sample presents an unseen label.
In other words, once the classification algorithm computes the partitions,
three disjoint events may occur to a new sample: $a)$ it is correctly labeled;
$b)$ it is mislabeled (occurring with probability $P_{ML}$); $c)$ it belongs
to an unseen class (with probability $P_{NL}$). The two latter events entail a
misclassification, hence we can write the bounds of Theorem 1 as

$\displaystyle\mathbb{P}^{N}\left[P_{ML}+P_{NL}\leq\overline{\epsilon}(s^{*},N,\beta)\right]>1-3\beta.$
(21)

As such, after collecting $N$ samples, we solely account for the labels that
the algorithm witnesses, set $L$ as the number of different seen labels, and
proceed to solve optimisation problem (16). Theorem 1 retains its validity
also in presence of unseen labels, if we consider all samples belonging to any
omitted class as misclassified; in practical terms, we should directly add
them to $s^{*}$. Indeed, the scenario approach concerns the number of violated
constraints: in principle, we could purposely exclude any label and its
corresponding samples and Theorem 1 could be applied as long as we account for
these samples as misclassifications.

Once the CM-SVM program (16) is solved, we use the resulting partitions to
assign a label to any (new) sample of interest. The label corresponds to an
abstract state, which is used as initial state for the $\ell$-CTA: we then
compute the SAC and LAC (see (7)) as lower and upper bounds for the
corresponding AIST. The gap between the SAC and LAC offers additional
information, as $\delta_{AIST}=LAC-SAC$ defines the precision of our
abstraction: the true AIST dwells within the interval $\delta_{AIST}$,
therefore the tighter $\delta_{AIST}$ is, the more precise the information we
gather. If needed, we may increase $\ell$ to refine the abstraction. In this
sense, $\ell$ can be seen as a tradeoff: a large $\ell$ provides a larger
state space of the S$\ell$-CA, herald of a higher computational cost, along
with more precise bounds. Further, in order to provide a global precision of
the abstraction, we define the EAC (expected average cycle) as the average
$\delta_{AIST}$ over all states; formally,

$EAC:=\frac{1}{|\mathcal{X}|}\sum_{x\in\mathcal{X}}\delta_{AIST}(x).$ (22)

The EAC metric embodies the degree of uncertainty in the evaluation of the
AIST for every possible state of the abstraction. A smaller EAC ensures a more
precise abstraction.

##  IV Experimental Evaluation

We show the effectiveness of our method considering a 2-D and a 4-D linear
system, and comparing against a model-based technique, in order to validate
our results and evaluate their precision and computational cost.

We collect $N=10^{4}$ random samples $Q_{i}=(\mathbf{X}_{i},\mathbf{Y}_{i})$,
evaluated from the 2-D linear system in [7, 6],

$\displaystyle\dot{\xi}(t)=A\xi(t)+Bu(t),$ (23) $\displaystyle
A=\begin{bmatrix}0&1\\\ -2&3\end{bmatrix},\quad B=\begin{bmatrix}0\\\
1\end{bmatrix},\quad K=\begin{bmatrix}0&-5\end{bmatrix},$

with triggering condition $|\xi(t)-\hat{\xi}(t)|^{2}>\sigma^{2}|\xi(t)|^{2}$,
where $\sigma=0.1$. We obtain a dataset with 3 possible ISTs, i.e.
$\mathbf{Y}_{i}\in\\{1,2,3\\}$.

We fix the hyper-parameters of the optimisation program (16) as
$\beta=10^{-6}$, $\rho=10^{3}$. The train data are used to solve the
optimisation problem (16) and obtain the mapping from the concrete states
$\xi(\cdot)$ to the abstract states $x$. We collect the number of violated
constraints $s^{*}$ and compute the corresponding $\overline{\epsilon}$ bound
according to (19). Table I reports the number of labels $L$, the number of
violated constraints $s^{*}$, its corresponding bound $\overline{\epsilon}$
and the empirical percentage of violated constraints (computed on additional
$10^{4}$ samples) and finally the computational time of the CM-SVM algorithm,
for different combinations of $\ell$ and $\sigma$. As expected, the empirical
constraint violation percentage is smaller than $\overline{\epsilon}$ for all
experiments.

TABLE I: Performance of the CM-SVM algorithm.  |  |  |  |  | Empir. | CM-SVM
---|---|---|---|---|---|---
$\sigma$ | $\ell$ | $L$ | $s^{*}$ | $\overline{\epsilon}$ | Violat. | time [s]
0.1 | 1 | 3 | 99 | 0.020 | 1.14% | 1.4
| 5 | 19 | 212 | 0.034 | 2.75% | 9.0
| 10 | 34 | 325 | 0.048 | 3.90% | 77.9

We then construct the abstraction: considering several values of $\ell$, we
report the number of states $|\mathcal{X}|$, transitions $|\mathcal{E}|$, the
EAC in Table II. The increase of $\ell$, together with an obvious increase in
the number of states and transitions, provides a smaller EAC, in view of the
decrease of the abstraction’s non-determinism (the number of states approaches
the number of transitions). We challenge our data-driven methodology against a
model-based procedure developed in [6, 7, 8]. Comparing the two abstractions,
our procedure returns an almost equivalent transition system, smaller by few
states (and transitions): being sample-based, our abstraction may lack the
states belonging to a small, arguably negligible, portion of the state-space.
Nevertheless, the EAC remains very close to the model-based one.

TABLE II: Data-driven and model-based abstractions for the 2D model. Time is in seconds.  | Data-driven | Model-based
---|---|---
| $\ell$
---
1
5
10
| $|\mathcal{X}|$ | $|\mathcal{E}|$ | $\overline{\epsilon}$ | EAC | Time
---|---|---|---|---
3 | 9 | 0.020 | 2.0 | 2
19 | 24 | 0.034 | 2.0 | 9
34 | 39 | 0.048 | 1.0 | 78
| $|\mathcal{X}|$ | $|\mathcal{E}|$ | EAC | Time
---|---|---|---
3 | 9 | 2.0 | 5.9
7 | 17 | 2.0 | 3.6
34 | 39 | 0.97 | 3.1
TABLE III: Data-driven and model-based abstractions for the 3D (top) and 4D (bottom) systems. TO indicates a timeout.  | Data-driven | Model-based
---|---|---
| $\ell$
---
1
2
3
4
1
2
3
| $|\mathcal{X}|$ | $|\mathcal{E}|$ | $\overline{\epsilon}$ | EAC | Time
---|---|---|---|---
3 | 9 | 0.028 | 2 | 2
7 | 17 | 0.036 | 2 | 4
13 | 26 | 0.040 | 2 | 17
20 | 34 | 0.044 | 1.5 | 29
10 | 100 | 0.006 | 9 | 12
43 | 218 | 0.007 | 3.5 | 42
111 | 286 | 0.010 | 2.2 | 128
| $|\mathcal{X}|$ | $|\mathcal{E}|$ | EAC | Time
---|---|---|---
3 | 9 | 2 | 9
7 | 17 | 2 | 7
15 | 33 | 2 | 12
26 | 46 | 2 | 59
10 | 100 | 9 | 6
100 | 1000 | 9 | 9
- | - | - | TO

We finally challenge our procedure with a 3D and a 4D models as proposed in
[5, 7]. For this case study we generate $N=2\cdot 10^{4}$ samples. We apply
our procedure for $\ell=1,2,3$, and report the results in Table III in terms
of the resulting abstraction (number of states and transitions, EAC). We
notice that the procedure computational time remains reasonable for every
test, despite the large number of labels. The model-based procedure, on the
other hand, exploits the knowledge of the system model to eliminate the
transitions and states that are not permitted by the triggering condition.
This inspection causes the increase of computational time for a large $\ell$,
until it reaches the 10 minute time out.

##  V Conclusions and Future Works

We have presented a method to estimate the sampling performance of an unknown
PETC system, namely its average inter-sample time, by means of a data-driven
abstraction. We extend the scenario approach to multiclass SVM algorithms and
build an $\ell$-complete abstraction to return bounds on the AIST. We
challenge our procedure against model-based state-of-the-art tools: the data-
driven approach is computationally faster for high dimensional systems whilst
providing tight probabilistic guarantees. Our methodology suffers from the
limitations of the SVM algorithms: the capability of finding good hyperplanes
deteriorates in the presence of a large number of labels. Nevertheless, we
offer tight results for the benchmarks at hand. Future work includes the
application of this methodology to noisy, nonlinear systems. We also aim at
extending the scenario approach to neural classifiers to overcome the
limitations of SVM.

## References

  * [1] K. J. Astrom and B. M. Bernhardsson, “Comparison of riemann and lebesgue sampling for first order stochastic systems,” in Proceedings of the 41st IEEE Conference on Decision and Control, 2002., vol. 2, pp. 2011–2016, IEEE, 2002.
  * [2] P. Tabuada, “Event-triggered real-time scheduling of stabilizing control tasks,” IEEE Transactions on Automatic Control, vol. 52, no. 9, pp. 1680–1685, 2007.
  * [3] A. S. Kolarijani and M. Mazo, “Formal traffic characterization of lti event-triggered control systems,” IEEE Transactions on Control of Network Systems, vol. 5, no. 1, pp. 274–283, 2016.
  * [4] P. Tabuada, Verification and control of hybrid systems: a symbolic approach.  Springer Science & Business Media, 2009.
  * [5] G. d. A. Gleizer and M. Mazo Jr, “Scalable traffic models for scheduling of linear periodic event-triggered controllers,” IFAC-PapersOnLine, vol. 53, no. 2, pp. 2726–2732, 2020.
  * [6] G. d. A. Gleizer and M. Mazo, “Towards traffic bisimulation of linear periodic event-triggered controllers,” IEEE Control Systems Letters, vol. 5, no. 1, pp. 25–30, 2020.
  * [7] G. de A. Gleizer and M. Mazo Jr, “Computing the sampling performance of event-triggered control,” in Proceedings of the 24th International Conference on Hybrid Systems: Computation and Control, pp. 1–7, 2021.
  * [8] G. Delimpaltadakis, G. de Albuquerque Gleizer, I. van Straalen, and M. Mazo Jr., “Etcetera: beyond event-triggered control,” in Proceedings of the 25th International Conference on Hybrid Systems: Computation and Control, 2022.
  * [9] M. Cubuktepe, N. Jansen, S. Junges, J.-P. Katoen, and U. Topcu, “Scenario-based verification of uncertain mdps,” in International Conference on Tools and Algorithms for the Construction and Analysis of Systems, pp. 287–305, Springer, 2020.
  * [10] T. S. Badings, A. Abate, N. Jansen, D. Parker, H. A. Poonawala, and M. Stoelinga, “Sampling-based robust control of autonomous systems with non-gaussian noise,” arXiv preprint arXiv:2110.12662, 2021.
  * [11] M. Campi and S. Garatti, “The exact feasibility of randomized solutions of uncertain convex programs,” SIAM Journal on Optimization, vol. 19, no. 3, pp. 1211–1230, 2008.
  * [12] M. C. Campi, S. Garatti, and F. A. Ramponi, “A general scenario theory for nonconvex optimization and decision making,” IEEE Transactions on Automatic Control, vol. 63, no. 12, pp. 4067–4078, 2018.
  * [13] S. Garatti and M. C. Campi, “Risk and complexity in scenario optimization,” Mathematical Programming, pp. 1–37, 2019.
  * [14] M. C. Campi and S. Garatti, “Scenario optimization with relaxation: a new tool for design and application to machine learning problems,” in 2020 59th IEEE Conference on Decision and Control (CDC), pp. 2463–2468, IEEE, 2020.
  * [15] W. H. Heemels, M. Donkers, and A. R. Teel, “Periodic event-triggered control for linear systems,” IEEE Transactions on automatic control, vol. 58, no. 4, pp. 847–861, 2012.
  * [16] G. de Albuquerque Gleizer and M. Mazo Jr, “Chaos and order in event-triggered control,” arXiv e-prints, 2022.
  * [17] K. Chatterjee, L. Doyen, and T. A. Henzinger, “Quantitative languages,” ACM Transactions on Computational Logic (TOCL), vol. 11, no. 4, pp. 1–38, 2010\.
  * [18] R. M. Karp, “A characterization of the minimum cycle mean in a digraph,” Discrete mathematics, vol. 23, no. 3, pp. 309–311, 1978.
  * [19] J. Weston and C. Watkins, “Multi-class support vector machines,” tech. rep., Citeseer, 1998.
  * [20] M. Mazo, A. Anta, and P. Tabuada, “On self-triggered control for linear systems: Guarantees and complexity,” in 2009 European Control Conference (ECC), pp. 3767–3772, IEEE, 2009.
  * [21] C.-W. Hsu and C.-J. Lin, “A comparison of methods for multiclass support vector machines,” IEEE transactions on Neural Networks, vol. 13, no. 2, pp. 415–425, 2002.
  * [22] K. Crammer and Y. Singer, “On the algorithmic implementation of multiclass kernel-based vector machines,” Journal of machine learning research, vol. 2, no. Dec, pp. 265–292, 2001.