# Learning Formal Specifications from Membership and Preference Queries

Ameesh Shah  Marcell Vazquez-Chanlatte  Sebastian Junges  Sanjit A. Seshia

###### Abstract

Active learning is a well-studied approach to learning formal specifications,
such as automata. In this work, we extend active specification learning by
proposing a novel framework that strategically requests a combination of
membership labels _and pair-wise preferences_ , a popular alternative to
membership labels. The combination of pair-wise preferences and membership
labels allows for a more flexible approach to active specification learning,
which previously relied on membership labels only. We instantiate our
framework in two different domains, demonstrating the generality of our
approach. Our results suggest that learning from both modalities allows us to
robustly and conveniently identify specifications via membership and
preferences.

Preference-Based Learning, Formal Specifications, Specification Mining, Active
Learning, Grammatical Inference

##  1 Introduction

An emerging body of work advocates for the use of formal specifications to
model objectives of autonomous agents. Formal specifications provide a number
of benefits relative to Markovian rewards: they can specify non-Markovian
historical dependencies, they are composable, and they can be easily
transferred and understood across environments. Such specifications are
popular in planning, verification, and robotics (Webster et al., 2020; Yifru &
Baheri, 2023).

A popular approach to learning formal specifications is active learning,
querying a non-human membership oracle to label a generated trajectory as
either positive (belongs in the set of desired behaviors) or negative (Bastani
et al., 2018; Bongard & Lipson, 2005; Angluin, 1987). We aim to extend these
approaches to cases where we learn from non-expert human teachers.While asking
only membership queries suffices for completeness in active specification
learning, we expect existing approaches to be challenging for human oracles,
who are relatively bad at answering membership queries (Palan et al., 2019;
Burton et al., 2021; Phelps et al., 2015).

To address this challenge, we identify _preference querying_ as a promising
alternative to membership querying, where the human is asked to rank two
trajectories. Preferences are relatively inexpensive to obtain, are generally
preferred by human teachers, and are known to be less susceptible to
mislabeling than membership query responses (Palan et al., 2019; Burton et
al., 2021; Phelps et al., 2015). Moreso, the combination of the two signals is
promising: _Preference queries are comparatively more accurate but less
informative than membership queries_ (Palan et al., 2019).

In this work, we contribute a general framework that allows for active
learning from a combination of preferences and labeled examples. The framework
works as follows: First, from the known facts, it generates candidate
specifications consistent with previously observed membership and preference
constraints. The next step is to rule out hypotheses from this candidate set
that are consistent with the known information, but incorrect. This step is
realized by actively asking either a preference query or a membership query
chosen to gain information that will rule out incorrect candidate hypotheses.
From this point, we iteratively generate new candidate hypotheses that are
consistent with the newly updated facts, and continue asking queries until the
correct specification is found, if one exists. To robustify the algorithm
against a (limited) number of wrong answers, the algorithm can identify and
ignore inconsistent sets of answers.

Our experiments show that our automated query selection process can avoid a
substantial number of membership queries by asking additional preference
queries. This trade-off between queries can be easily configured by setting
the relative cost of answering each type of query to the teacher.

##### Contributions

We present the formalism of membership-preserving preferences that allows for
specification learning from oracles that can answer comparison and membership
queries. To show the feasibility and efficacy of our formalism, we propose a
_concept class agnostic_ algorithm for querying oracles and run empirical
evaluations on two different domains. Finally, we provide a novel SAT-based
encoding for identifying DFAs from labeled examples _and_ pair-wise
preferences.

##  2 Learning with Membership Respecting Preferences

We begin by developing the machinery to specify which behaviors within a set
are desirable, both in a relative and satisficing sense. For a given
_universe_ , $\mathcal{U}$, containing _atoms_ $x\in\mathcal{U}$, a formal
specification, or concept $\varphi\subseteq\mathcal{U}$, contains a set of
atoms. We denote by $\varphi(x)$ the indicator, $[x\in\varphi]$ and refer to a
collection of concepts, $\Phi$, as a _concept class_ 111 For simplicity, we
conflate a concept with its representation. . W.l.o.g., we assume that the
universe coincides with the union of the concepts in a concept class,
$\mathcal{U}=\bigcup\Phi$.

######  Example 1.

Concept classes and their universes can be finite or infinite. For example,
when representing formal task specifications, one takes as the (infinite)
universe, $\Sigma^{*}$, i.e., all words from a finite alphabet $\Sigma$.
Similarly, languages represented by classes of automata, e.g., DFAs, are
(infinite) concept classes.

fedcba$\varphi_{2}$$\varphi_{1}$ Figure 1:

Next, we formalize the notion of pairwise preferences on atoms via _preorders_
, $\preceq$, on universes, i.e., transitive and reflexive relations on
$\mathcal{U}$. Namely, we call a preorder on a universe a _preference order_
and interpret $x\preceq y$ as _“ $y$ may be preferred over $x$”_. We write
$x\prec y$ if $x\preceq y$ and not $y\preceq x$, interpreted as _“ $y$ _is_
preferred over $x$”_. Two atoms have equal preference, $x\equiv y$, if
$(x\preceq y)\wedge(y\preceq x)$. Finally, two atoms are _incomparable_ ,
$x\mid\mid y$, if $\neg(x\preceq y\vee y\preceq x)$.

######  Example 2.

An example preference order over the universe $\\{a,b,c,d,e,f\\}$, is shown in
Fig 1. It is represented using a directed acyclic graph, $H=(V,E)$ called a
_Hasse diagram_. The nodes of $H$ represent equivalence classes, i.e., for all
$v\in V$, $x,y\in v\implies x\equiv y$, and the edges of $H$ represent strict
preferences, i.e., $(x,y)\in E\implies x\prec y$. The full preference order is
the transitive reduction of $H$.

######  Example 3.

Costs and rewards offer a common way to define preference orders. For example,
let $x\in\mathcal{U}$ denote the set of paths through a maze and assign a
cost, $c(x)\in\mathbb{R}$, to each path based on its length. A natural
preference order is then given by comparing costs: $c(x)\leq c(y)$ implies
$y\preceq x$. This order is total (no atoms are incomparable) and illustrates
that two distinct atoms can have equal preference, i.e., $c(x)=c(y)$ implies
$x\equiv y$, but not $x=y$.

###  2.1 Learning with Preferences

We now turn our attention to identifying an unknown concept, $\varphi^{*}$.
Namely, we shall assume access to a _membership oracle_ ,
$\mathcal{M}\colon\mathcal{U}\to\\{\in,\notin\\}$, to evaluate if
$x\in\varphi^{*}$, as well as a comparison oracle,
$\mathcal{C}\colon\mathcal{U}^{2}\to\\{\prec,\|,\succ,\equiv\\}$, to provide
preferences between atoms, e.g., $[C(x,y)=\hskip 1.99997pt\prec]$ iff $[x\prec
y]$. Invocations of these oracles are _queries_.

Problem Statement: Let $\varphi$ be an _unknown_ specification in concept
class $\Phi_{\text{init}}$. Given membership and comparison oracles
$\mathcal{M}$ and $\mathcal{C}$, infer $\varphi$.

######  Remark 2.1.

For finite concept classes it suffices to consider only the membership oracle
$\mathcal{M}$, ignoring query and time complexity. In particular, one may
pair-wise consider all concepts and pose a membership query from the symmetric
difference of the concepts to uniquely identify the concept. However, for many
domains (Burton et al., 2021), obtaining accurate labels to realize the
membership oracles is expensive. The key question in this work is _how to
exploit the availability of the comparison oracle_ $\mathcal{C}$.

To leverage the comparison oracle, we relate preferences to membership in
$\varphi^{*}$. We therefore focus on preference orders that respect
membership: atoms outside of the concept, $x\not\in\varphi^{*}$, cannot be
preferred to atoms in the concept, $y\in\varphi^{*}$.

######  Definition 2.2.

A preference order is a _membership-respecting preference_ (MemReP) w.r.t.
$\varphi$ if

$x\preceq y\implies\varphi(x)\leq\varphi(y).$ (1)

######  Example 4.

All preference orders are membership respecting w.r.t. concepts
$\top\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
def}}}}{{=}}}\mathcal{U}$ and
$\bot\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
def}}}}{{=}}}\emptyset$. Similarly, any oracle that yields $C(x,y)=\|$ for all
$x,y\in\mathcal{U}$ is vacuously membership-respecting.

######  Example 5.

Cost based preferences, like in our path example, together with thresholded
cost concepts, i.e.,
$\varphi_{\delta}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
def}}}}{{=}}}\\{x~{}\in~{}\mathcal{U}\ :\ c(x)\leq\delta\\},$ for some cost
map $c\colon\mathcal{U}\to\mathbb{R}$ and threshold $\delta\in\mathbb{R}$, are
membership respecting.

######  Example 6.

We continue with Ex. 2. This order is membership-preserving for
$\varphi_{1}=\\{a,b\\}$, but not for $\varphi_{2}=\\{d,e\\}$. Graphically,
$\varphi_{2}$ is not membership-preserving as there is an edge from
$\bar{\varphi_{2}}$ to $\varphi_{2}$.

Example 6 illustrates that the MemReP assumption is sometimes strong enough to
distinguish concepts without any membership queries. Namely, if there exists a
pair of atoms, $x\in\varphi_{1}\setminus\varphi_{2}$ and
$y\in\varphi_{2}\setminus\varphi_{1}$, such that $\mathcal{C}(x,y)\neq||$,
then $\mathcal{C}(x,y)$ is guaranteed to distinguish $\varphi_{1}$ and
$\varphi_{2}$ under the MemReP assumption.

######  Definition 2.3.

Let $X=(X_{\mathcal{M}},X_{\mathcal{C}})$ be a tuple of sets of membership and
comparison labeled examples respectively, e.g.,

$\displaystyle X_{\mathcal{M}}=\\{(x_{1},\in),\ldots,(x_{j},\notin)\\}$
$\displaystyle
X_{\mathcal{C}}=\\{(x_{k},y_{k},\|),\ldots,(x_{n},y_{n},\prec)\\}.$

A concept $\varphi$ is _consistent_ with $X$ if (i) $\varphi$ agrees with all
membership assignments in $X_{\mathcal{M}}$, e.g., $(x,\in)\in
X_{\mathcal{M}}\implies x\in\varphi$; and (ii) All preferences in
$X_{\mathcal{C}}$ are membership respecting under $\varphi$, e.g.,
$(x,y,\prec\varphi(x)\leq\varphi(y)$. Given a concept class $\Phi$, we denote
by $\Phi^{X}$ the set of all concepts in $\Phi$ consistent with $X$.

###  2.2 Abstract Algorithm

We now return to the problem of identifying an unknown concept given access to
a membership oracle and a membership respecting comparison oracle. In Alg. 1,
we outline the general process for learning concepts from _finite_ concept
classes given such oracles. The learner begins with a concept class, asks a
membership or comparison query, and then removes concepts that are
inconsistent with the query result until a unique concept remains.

Algorithm 1 Generic algorithm for concept identification.

1: Assign $\Phi$ as the initial concept class $\Phi_{\text{init}}$.

2: Initialize the set of labeled examples $X$ as $(\emptyset,\emptyset)$.

3: while $|\Phi|>1$ do

4: Ask either a membership or a comparison query given $X$ and $\Phi^{X}$.

5: Add the result to $X$.

5: $\Phi^{X}${$\Phi^{X}=\emptyset$ or $\Phi^{X}=\\{\phi^{*}\\}$.}

######  Proposition 2.4.

Suppose for every iteration, the probability of asking a distinguishing
membership query, i.e., asking $\mathcal{M}(x)$ for $x$ in the symmetric
difference of two concepts in $\Phi^{X}$, is bounded from below. Then, Alg 1
almost surely terminates.

######  Remark 2.5.

To treat infinite concept classes, we appeal to Occam’s Razor, and seek to
find the “simplest” concept that is consistent with the data. Formally, we
assume that the finite concept class is the (countably infinite) union of
finite concept classes, $\Phi=\bigcup_{i=1}^{\infty}\Phi_{i},$ where $i$, is
taken as a complexity measure, e.g, number of states of an automaton. We
extend the above process by seeking to find the smallest $i$ such that the
above process returns a singleton. Finally, as is standard in this setting, we
will additionally assume access to an equivalence oracle to provide
completeness guarantees. In practice, such equivalence queries are often
impractical, and are approximated via conformance testing and sampling.

In order to realize this algorithm in practice, we require three ingredients.
First, we must develop methods that can synthesize a consistent concept over
both membership query and preference query results for a specific concept
class. This operation enables symbolically interacting with $\Phi^{X}$ in Alg.
1. We provide synthesis methods for the concept classes used in our
experiments in the appendix. Second is an intelligent means to select a query
for $\mathcal{M}$ or $\mathcal{C}$, which we expand on in the sequel. Last is
a means to non-trivial possibility of labeling mistakes, which we provide in
the appendix.

##  3 Asking the right queries

In the sequel, we discuss a (concept class agnostic) strategy to select
queries for an efficient version of Alg. 1.

###  3.1 Cost model

Before we optimize our algorithm, we must set the measure that we aim to
optimize. In any active learning algorithm, the selection of the queries is
central to its performance. In particular, we seek to balance minimizing the
number of queries asked and computational costs. To this end, we model the
costs of preference and membership queries to be time invariant and constant,
based on a weighted sum:

$\text{cost}(\text{queries})\triangleq
a\cdot\\#\text{mem}+b\cdot\\#\text{pref},$ (2)

where $\\#$mem and $\\#$pref refer to the number of membership and preference
queries and $a,b\in\mathbb{R}_{\infty}$. For example, $a=b$ treats membership
and comparisons interchangeably and $a=\infty,b=1$ lexicographically prefers
comparisons over membership queries222Our algorithm can handle arbitrary cost
models over $\\#$mem and $\\#$pref and is not dependent on the specific
structure of equation 2..

###  3.2 Contextual Bandit Formulation

Because the results of the queries are a priori unknown, naïvely optimizing a
given cost model is often infeasible. Furthermore, as the next example
illustrates, adversarial teachers can induce arbitrary regret.

######  Example 7.

Recall the lexicographic example, $a=\infty,b=1$. If all preferences yield
incomparable, then one would regret making any comparison queries. On the
other hand, if one ignores comparisons, but the underlying preference lattice
is total as in Ex. 5, then one may ask many more membership queries than is
required. In particular, if the (total) preference order were known, then the
learner could binary search (using $\mathcal{M}$) for the unique point where
membership changes.

Further, we highlight that, even if a model for query responses is known,
optimally planning a sequence of queries is often computationally intractable.
There are $M=\binom{|\mathcal{U}|}{2}+\mathcal{U}$ queries to ask in a single
step, and thus roughly $3^{M^{t}}$ possible combinations when asking up to $t$
queries. Thus, even assuming $\mathcal{U}$ is finite, but non-trivially small,
e.g., strings of length at most 10, the search space quickly becomes
intractable.

Thus, we propose a two stage formulation to optimize the query selection based
on adversarial contextual multi-armed bandits (CMABs) (Auer et al., 2002),
specifically, multi-armed bandits with expert advice. In this formulation, the
classic multi-armed bandit framework is extended by introducing experts that
consider the arms and context in the problem, and provide recommendations in
the form of probability distributions over the arms that our algorithm can
then make use of in its policy. In order to instantiate our CMAB algorithm
with experts, we make the following choices: (i) We use a heuristic to select
candidate comparison and membership queries, the _arms_ in our formulation.
The heuristic is a (Monte Carlo) estimate of the concept class size’s
reduction for each query’s possible outcome. (ii) We define a (bounded) proxy
cost per arm weighing the query cost against the (estimated) reduction in the
concept class:

$\text{loss}_{c}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
def}}}}{{=}}}\frac{c}{\max(a,b)}\cdot\frac{|\Phi^{\prime}|}{|\Phi|}\in[0,1],$
(3)

where $c$ is the cost of selected arm’s query type (thus either $a$ or $b$).
Finally, (iii) we encode two heuristic query strategies as _experts_ assigning
probabilities to each arm, described in Section 3.3. The resulting CMAB game
proceeds in rounds described in Alg. 2, each round corresponds to an iteration
in Alg. 1.

Algorithm 2 CMAB round for selecting a query.

1: Select comparison and membership queries via Alg. 3.

2: Estimate the loss (3) for different query outcomes.

3: Provide average and worst-case expert advice distributions on the arms
(queries), $E_{1},E_{2}$, see Sec. 3.3.

4: Sample which expert, $E\sim\\{E_{1},E_{2}\\}$, to listen to based on the
historical performance of the expert.

5: Sample the arm (query) based on $E$’s arm distribution.

6: Compute the actual loss and update expert distributions.

Algorithm 3 Query selection heuristic.

1: Select a set of up to $\alpha$ unrefuted concepts, $\Psi\subseteq\Phi$.

2: Let $X$ be a set of atoms such that (i) $|X|\ \in[\alpha,\beta]$ and (ii)
$X$ distinguishes concepts in $\Psi$, i.e.
$\forall\varphi_{1},\varphi_{2}\in\Psi~{}.~{}\exists x\in
X~{}.~{}x\in\varphi_{1}\Delta\varphi_{2}.$

3: Find $x\in X$ that minimizes the (worst-case) number of concepts in $\Psi$
that are consistent after $\mathcal{M}(x)$.

4: Find $y,z\in X$ that minimize the (worst-case) number of concepts in $\Psi$
that are consistent after $\mathcal{C}(y,z)$.

5: Return candidate queries $\langle\mathcal{M}(x),\mathcal{C}(y,z)\rangle$.

To avoid considering all atoms in $\mathcal{U}$, we propose the concept class
agnostic heuristic in Alg. 3 to select candidate membership and comparison
queries. For our implementation, we use $\alpha=2$, and take at most two atoms
per concept, i.e., $\beta=2\alpha$.

###  3.3 Worst and average case advice

We propose to give advice towards either of the two queries based on combining
two perspectives. In particular, we propose to use the following two experts
with the following advice arm distributions: (1) Pessimistic: Weighs each arm
by its worst-case loss. Ignores the incomparable answer for preference
queries. (2) Historical: Weighs each arm by its expected loss, computed by
averaging the previous losses incurred by pulling that particular arm.

To construct the advice distribution, we take the softmax of the weights of
the comparison and membership queries. The expert selection distribution is
then updated using the standard exp4 contextual bandit algorithm (Auer et al.,
2002) which guarantees that we will switch between our pessimistic and
historical arm strategy in a manner such that, with respect to loss (3), the
algorithm would not have done much better sticking to advice from a single
expert.

Let us share the following intuitions for our choice of experts. The
pessimistic expert helps to ensure some notion of progress. However, as an
incomparable answer for the comparisons never yields any progress, we exclude
this case from the expert. On the other hand, we have seen in Ex. 7 that the
utility of a comparison query depends heavily on the oracle’s underlying
preference order. To capture this observation, the historical expert learns
whenever almost all comparisons yield incomparable and will promote using
membership in these cases. Likewise, this expert will discover when there is a
total preference order and all atoms are comparable, and perhaps even
equivalent. Finally, observe the following proposition about the proposed
algorithm:

######  Proposition 3.1.

Assume the unknown concept, $\varphi^{*}$, is in $\Phi$. Running Alg 1 using
Algs 3,2 for queries (almost surely) identifies $\varphi^{*}$ after finite
queries.

A proof sketch for Prop. 3.1 is provided in the appendix.

##  4 Experiments

In this section, we instantiate Alg. 1 on two families of concept classes,
demonstrating the flexibility and efficacy of the proposed formalism and
heuristics.

###  4.1 Deterministic Finite Automata

To begin, we apply the algorithm and operations outlined in Sec. 3 to the
space of DFA identification, relying on the performance of modern Boolean
satisfiability (SAT) solvers.

BlBrRYYRR

Figure 2:

A _Deterministic Finite Automaton_ , DFA, is a 5-tuple,
$(Q,\Sigma,\delta,q_{0},F)$, consisting of a finite set $Q$ of _states_ , a
finite _alphabet_ $\Sigma$, a _transition function_ , $\delta\colon
Q\times\Sigma\to Q$, an _initial state_ $q_{0}$, and the _accepting states_
$F\subseteq Q$. The function $\delta^{*}\colon\Sigma^{*}\to Q$ denotes the
lifting of $\delta$ to sequences of symbols (strings), via repeated
application. Finally, the language of DFA
$\mathcal{D}=\\{w\in\Sigma^{*}\mid\delta^{*}(w)\in F\\}$ is set of strings
that reach an accepting state, $q\in F$.

##### Learning Task Specifications for Robots

We study the problem of conveying a task to an agent (robot) moving about an
environment. For example, consider the task specification that says “avoid red
(lava) tiles and do reach a yellow (recharge) tile (RY)” and “between visiting
blue (water) tiles and yellow tiles, the agent must be visit a brown (dryer)
tile. (BBY)” from (Vazquez-Chanlatte et al., 2018). This task specification is
described by the DFA shown in Fig 2. We assume that the robot is pre-
programmed to universally assume that a task will contain the RY constraint
and seeks to interactively learn the domain-specific BBY constraint (in the
form of a DFA) from a user.

First, observe that because DFAs are closed under conjunction, a new DFA can
be easily derived that will not violate the a priori specified RY task.
Further, depending on the system dynamics, the user may prefer some traces to
others, and is able to provide these pair-wise comparisons. Thus, we pose this
task learning process as an active learning problem, where the user can
provide (i) _pair wise preferences_ and (ii) _membership query responses
(labels)_ that specify whether an example is good or bad. We want to leverage
that query mechanism to potentially accelerate or robustify the learning of
the DFA.

The oracle uses a randomly generated membership respecting preference order,
where approximately $\nicefrac{{1}}{{10}}$ of the comparisons yield
incomparable. To refute equivalence queries, we sample a random string from
the symmetric difference of the true DFA and the current hypothesis. Finally,
we fix the comparison cost to 1 and vary the membership cost to study the
trade off in queries the algorithm makes.

Figure 3: Trade-off between query types for DFAs. The bars show the
contribution of membership (red), preference (blue), and equivalence (green)
queries.

The results of the experiment are shown in Fig 3. We observe that, as
expected, as the membership cost increases (i) the total number of queries
increases (ii) the total number of membership queries decreases. Specifically,
_removing 1 membership query adds an average of 2.03 preference queries_ each
time the cost doubles. Additionally, the use of preference queries allows the
use of membership queries to be well below the baseline rate of setting the
costs such that only membership queries are used; that is, setting the cost of
a preference to $\infty$.

Finally, we compare with the discriminate tree variant of L* (Kearns &
Vazirani, 1994; Angluin, 1987), a classic algorithm for learning DFAs from
membership and equivalence queries. We use the AALpy library (Muškardin et
al., 2022) implementation of L*, and find that the implementation requires 11
membership queries and 2 equivalence queries (the same number as Fig 4) that
cannot be answered by the RY task prior knowledge. While our algorithm
requires more overall queries, we observe that the number of membership
queries can be fewer than 11 as at membership cost 4, all without concept
class specific tailoring. Furthermore, we remark that these two algorithms
could be used in concert by adapting the membership query selection to use L*
provided queries.

##### Additional Experiments

In order to further study the performance of our algorithm in learning DFAs,
we performed the following studies: First, we applied our algorithm to
learning the Tomita Language DFAs, a standard benchmark in DFA learning, to
evaluate performance across a diversity of DFAs. Next, we evaluated our
algorithm on classes of DFAs that vary in size to evaluate how our algorithm
scales as the target DFA increases in complexity. Finally, we implemented and
evaluated a method in our algorithm that can identify and tolerate incorrect
responses from our oracle. The full details and results of these experiments
are available in the appendix.

###  4.2 Monotone Predicate Families

Next, we study monotone predicate families. A _monotone predicate family_ is a
concept class with an (arbitrary but fixed) partial order $\sqsubset$ defined
over the concepts such that $\varphi\sqsubset\varphi^{\prime}$ implies
$\varphi\subseteq\varphi^{\prime}$. Increasing a concept thus monotonically
increases the set of atoms included by the concept. We motivate studying
monotone predicates using a series of motivating examples.

######  Example 8.

We consider the on-boarding process of a hypothetical car that queries the
user to learn what (safe) distances to other objects they deem comfortable. In
the scope of this paper: (a) The resulting behavior should _never_ violate any
pre-defined safety constraints. (b) The on-boarding experience should be
brief, i.e., the system should try to minimize the number of queries. (c)
Communication should be unambiguous and concrete to cover edge cases.

The be above example can be cast as a 2-dimensional monotone predicate family,
where one dimension corresponds to maximum time, $\tau\in[0,T]$, the user is
willing to wait to reach the destination and the other dimension corresponds
to the minimum distance, $d\in[0,D]$, to another car the user is comfortable
with. The corresponding partial order has
$(\tau,d)\sqsubset(\tau^{\prime},d^{\prime})$ if $\tau<\tau^{\prime}$ and
$d>d^{\prime}$.

Figure 4: Trade-off between query types for monotone predicate functions. The
bars show the contribution of membership (red), preference (blue), and
equivalence (green) queries.

We seek to understand the trade-off between membership and comparisons
incurred by our algorithm given different membership and comparison costs. We
instantiated our algorithm with a size-indexed concept class, where each
$\Phi_{i}$ corresponds to a uniform 2d grid of parameters with $i$ points per
axis. Equivalence queries provide a labeled bi-partition separating the
concept. Like with our DFA experiment, the preference order was randomly
generated such that approximately $\nicefrac{{1}}{{10}}$ on atoms are
incomparable and approximately $\nicefrac{{1}}{{3}}$ of atoms whose preference
is not forced by the MemReP condition are strictly ordered. Furthermore, as a
baseline, we compare against an learner that only uses equivalence and
membership queries by setting the comparison query cost sufficiently high.

Fig. 4 shows the averaged results on 100 randomly generated concepts with the
comparison cost fixed to 1 and the membership cost changing on the horizontal-
axis. The vertical axis corresponds to the average of number of queries across
all preference orders. First, the average number of equivalence queries was
the same for each instance on the same concept, including the shown membership
only base-line. Furthermore, as desired, increasing the cost of the membership
queries results in the average number of membership queries decreasing, at the
expense of additional comparison queries: as the relative cost doubles,
removing 1 membership query adds on average 2.4 membership queries. This is
expected given that comparisons provide less information about the concept’s
label than a membership query.

We also observe that initially, introducing preferences occasionally
_increases_ the number of membership queries. This effect is due to: (i) the
greedy nature of our algorithm, meaning that “good” membership queries are
ignored as they correlate with “good” preference queries, and (ii) our
hyperparameters - namely the temperature of the softmax in the expert advice -
was tuned with the assumption that membership would cost significantly more
than preferences.

##  5 Related Work

This work is related to (i) Learning reward from preferences and (ii)
Grammatical inference and concept learning.

##### Active learning of rewards using preferences.

Inverse reinforcement learning (IRL) (Ng & Russell, 2000; Abbeel & Ng, 2004)
often relies on high-quality demonstrations to learn a reward function. More
recently, works have proposed approaching IRL from an active learning
perspective, asking a teacher for information-rich feedback on learner-
generated examples, such as corrected examples or labels on sections of
generated examples (Hadfield-Menell et al., 2016; Brown et al., 2018).
Preference-based reward learning has emerged from these active approaches as a
popular method due to the accuracy and relative inexpensiveness of preference
queries (Holladay et al., 2016; Wilson et al., 2012). To overcome the limited
information content gained from relative comparisons, various techniques have
been devised to actively select preference queries that maximize the amount of
information gained (Sadigh et al., 2017; Biyik & Sadigh, 2018; Xu et al.,
2017; Basu et al., 2019; Xu et al., 2020), typically by removing maximal
volume from the hypothesis space.

##### Grammatical inference and concept learning.

Grammatical inference (De la Higuera, 2010) refers to the rich literature on
learning a formal grammar (often an automaton) from data. Examples include
learning the smallest automata consistent with a set of positive and negative
strings (De la Higuera, 2010) or learning an automaton using membership and
equivalence queries (Angluin, 1987). Within this literature, the key
contributions of our work are to take into account preferences via the
concept-agnostic framework. Finally, our algorithm can be seen as an extension
of version space learning (Sverdlik & Reynolds, 1992), where we use
preference-based learning to build on existing methods that leverage either
explicit data structures or SAT-based DFA-identification (Ulyantsev et al.,
2015; Heule & Verwer, 2010) to realize candidate elimination.

##  6 Conclusion and Future Work

In this paper, we present a generic framework for learning task specifications
(concepts) from actively acquired from (noisy) preferences and labeled
examples. Despite being concept class agnostic, we demonstrated the efficacy
of our approach on two very different concept classes.

Nevertheless, interesting future work includes considering principled
approaches to deriving domain-specific optimizations of the heuristics used in
our framework. Furthermore, we hope to consider more expressive concept class
families such as symbolic automata and context-free grammars: With symbolic
automata we hope to support a mix of thresholded rewards and DFAs.

## References

  * Abbeel & Ng (2004) Abbeel, P. and Ng, A. Y.  Apprenticeship learning via inverse reinforcement learning.  In _ICML_ , volume 69 of _ACM International Conference Proceeding Series_. ACM, 2004.
  * Angluin (1987) Angluin, D.  Learning regular sets from queries and counterexamples.  _Inf. Comput._ , 75(2):87–106, 1987.
  * Auer et al. (2002) Auer, P., Cesa-Bianchi, N., Freund, Y., and Schapire, R. E.  The nonstochastic multiarmed bandit problem.  _SIAM J. Comput._ , 32(1):48–77, 2002.
  * Bastani et al. (2018) Bastani, O., Sharma, R., Aiken, A., and Liang, P.  Active learning of points-to specifications.  In Foster, J. S. and Grossman, D. (eds.), _Proceedings of the 39th ACM SIGPLAN Conference on Programming Language Design and Implementation, PLDI 2018, Philadelphia, PA, USA, June 18-22, 2018_ , pp. 678–692. ACM, 2018.  doi: 10.1145/3192366.3192383.  URL https://doi.org/10.1145/3192366.3192383.
  * Basu et al. (2019) Basu, C., Bıyık, E., He, Z., Singhal, M., and Sadigh, D.  Active learning of reward dynamics from hierarchical queries.  In _IROS_ , pp. 120–127, 2019.  doi: 10.1109/IROS40897.2019.8968522.
  * Biyik & Sadigh (2018) Biyik, E. and Sadigh, D.  Batch active preference-based learning of reward functions, 2018.
  * Bongard & Lipson (2005) Bongard, J. C. and Lipson, H.  Active coevolutionary learning of deterministic finite automata.  _J. Mach. Learn. Res._ , 6:1651–1678, 2005.  URL http://jmlr.org/papers/v6/bongard05a.html.
  * Brown et al. (2018) Brown, D. S., Cui, Y., and Niekum, S.  Risk-aware active inverse reinforcement learning.  In _CoRL_ , volume 87 of _Proceedings of Machine Learning Research_ , pp. 362–372. PMLR, 2018.
  * Burton et al. (2021) Burton, N., Burton, M., Fisher, C., Peña, P. G., Rhodes, G., and Ewing, L.  Beyond likert ratings: Improving the robustness of developmental research measurement using best–worst scaling.  _Behavior Research Methods_ , Apr 2021.  ISSN 1554-3528.  doi: 10.3758/s13428-021-01566-w.  URL https://doi.org/10.3758/s13428-021-01566-w.
  * De la Higuera (2010) De la Higuera, C.  _Grammatical inference: learning automata and grammars_.  Cambridge University Press, 2010.
  * Hadfield-Menell et al. (2016) Hadfield-Menell, D., Russell, S. J., Abbeel, P., and Dragan, A. D.  Cooperative inverse reinforcement learning.  In _NeurIPS_ , pp. 3909–3917, 2016.
  * Heule & Verwer (2010) Heule, M. and Verwer, S.  Exact DFA identification using SAT solvers.  In _ICGI_ , 2010.
  * Holladay et al. (2016) Holladay, R., Javdani, S., Dragan, A., and Srinivasa, S.  Active comparison based learning incorporating user uncertainty and noise.  In _Proceedings of RSS Workshop on Model Learning for Human-Robot Communication_ , June 2016.
  * Kearns & Vazirani (1994) Kearns, M. J. and Vazirani, U. V.  _An Introduction to Computational Learning Theory_.  MIT Press, 1994.
  * Muškardin et al. (2022) Muškardin, E., Aichernig, B., Pill, I., Pferscher, A., and Tappler, M.  Aalpy: an active automata learning library.  _Innovations in Systems and Software Engineering_ , 18:1–10, 03 2022.  doi: 10.1007/s11334-022-00449-3.
  * Ng & Russell (2000) Ng, A. Y. and Russell, S. J.  Algorithms for inverse reinforcement learning.  In _ICML_ , pp. 663–670. Morgan Kaufmann, 2000.
  * Palan et al. (2019) Palan, M., Shevchuk, G., Landolfi, N. C., and Sadigh, D.  Learning reward functions by integrating human demonstrations and preferences.  In _Robotics: Science and Systems_ , 2019.
  * Phelps et al. (2015) Phelps, A. S., Naeger, D. M., Courtier, J. L., Lambert, J. W., Marcovici, P. A., Villanueva-Meyer, J. E., and MacKenzie, J. D.  Pairwise comparison versus likert scale for biomedical image assessment.  _AJR. American journal of roentgenology_ , 204(1):8–14, Jan 2015.  ISSN 1546-3141.  doi: 10.2214/AJR.14.13022.
  * Sadigh et al. (2017) Sadigh, D., Dragan, A. D., Sastry, S., and Seshia, S. A.  Active preference-based learning of reward functions.  In _RSS_ , 2017.
  * Sverdlik & Reynolds (1992) Sverdlik, W. and Reynolds, R. G.  Dynamic version spaces in machine learning.  In _ICTAI_ , pp. 308–315. IEEE CS, 1992.
  * Tomita (1982) Tomita, M.  Learning of construction of finite automata from examples using hill-climbing : Rr: Regular set recognizer.  1982\.
  * Ulyantsev et al. (2015) Ulyantsev, V., Zakirzyanov, I., and Shalyto, A.  Bfs-based symmetry breaking predicates for DFA identification.  In _LATA_ , volume 8977 of _LNCS_ , pp. 611–622. Springer, 2015.
  * Vazquez-Chanlatte et al. (2018) Vazquez-Chanlatte, M., Jha, S., Tiwari, A., Ho, M. K., and Seshia, S. A.  Learning task specifications from demonstrations, 2018.
  * Webster et al. (2020) Webster, M., Western, D. G., Araiza-Illan, D., Dixon, C., Eder, K., Fisher, M., and Pipe, A. G.  A corroborative approach to verification and validation of human-robot teams.  _Int. J. Robotics Res._ , 39(1), 2020.  doi: 10.1177/0278364919883338.  URL https://doi.org/10.1177/0278364919883338.
  * Wilson et al. (2012) Wilson, A., Fern, A., and Tadepalli, P.  A bayesian approach for policy learning from trajectory preference queries.  In _NIPS_ , pp. 1142–1150, 2012.
  * Xu et al. (2017) Xu, Y., Zhang, H., Singh, A., Miller, K., and Dubrawski, A.  Noise-tolerant interactive learning from pairwise comparisons, 2017.
  * Xu et al. (2020) Xu, Y., Chen, X., Singh, A., and Dubrawski, A.  Thresholding bandit problem with both duels and pulls, 2020.
  * Yifru & Baheri (2023) Yifru, L. and Baheri, A.  Joint learning of policy with unknown temporal constraints for safe reinforcement learning.  _CoRR_ , abs/2305.00576, 2023.  doi: 10.48550/arXiv.2305.00576.  URL https://doi.org/10.48550/arXiv.2305.00576.

## Appendix

###  A MemRePs for DFAs

In order to realize our algorithm for DFA learning, we need to support
synthesizing a DFA consistent with _labeled examples_ $V_{+},V_{-}$ and an
observed set of preferences, $V_{\prec}$, i.e. the results of previously
observed membership and comparison queries respectively.

We extend the SAT encoding presented in (Ulyantsev et al., 2015; Heule &
Verwer, 2010) for the passive identification of DFAs from positive and
negative examples to support membership respecting preferences. The encodings
operate by using the provided positive and negative examples to form a prefix
tree. The nodes indexed by positive and negative examples are annotated with
whether they accept or reject. Two states can be merged if they are
indistinguishable in the resulting transition system. This feature, together
with the determinism of a DFA, are captured by transforming the problem into a
k-color graph coloring problem, where $k$ is the fixed size of the DFA that is
to be identified. The resulting graph coloring problem is then encoded as a
Boolean satisfiability (SAT) query. More specifically, for each labeled word,
$v$, the SAT encoding includes (i) a variable $x_{v,i}$ indicating if word $v$
accesses state (color) $i$ and (ii) a variable $z_{i}$ indicating whether
state (color) $i$ is accepting.

#### Encoding

We extend the existing encoding to incorporate membership respecting
preferences. Using these variables, a membership preserving preference,
$(w,v)\in V_{\prec}$, can be encoded using the following constraints:

$\forall i,j~{}.~{}(w\prec_{\varphi}v)\in
V_{\prec}:\quad\underbrace{(x_{w,j}\wedge x_{v,i})}_{v~{}\&~{}w\text{ access
}i~{}\&~{}j}\implies\underbrace{(z_{j}\implies z_{i})}_{z_{j}\implies
z_{i}\text{ is equiv to }z_{j}\leq z_{i}}$ (4)

This constraint formalizes the previously mentioned logic that non-preferred
trajectories’ acceptance will lead to preferred trajectories’ acceptance, and
preferred trajectories’ rejection will lead to non-preferred trajectories’
rejection. If this were not the case, the MemReP condition would lead to a
contradiction.

###  B MemRePs for Monotone Predicate Families

Recall the motivating example mentioned in section 8 that we cast as a
2-dimensional monotone predicate family. We provide additional insight
regarding our algorithm in the context of monotone predicate families as
follows.

##### Geometric Perspective

In order to study the generic behavior of our algorithm on monotone predicate
families, it helps to focus on a geometric interpretation of the concept
class. For that, we assume that we adequately parameterize the concepts in a
concept class $\Phi=\\{\varphi_{\theta}\mid\theta\in[0,1]^{d}\\}$. The
parameters $\theta$ induce a natural pointwise (or product) order $<$ with
$\theta<\theta^{\prime}$ if for all
$i<d~{}.~{}\theta_{i}<\theta^{\prime}_{i}$. It is then straightforward to
define the order on the concepts as
$\varphi_{\theta}\sqsubset\varphi_{\theta^{\prime}}$ if
$\theta<\theta^{\prime}$. Next, observe that any atom, $x\in\mathcal{U}$,
partitions the parameter space into two regions,

$\Theta^{+}_{x}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
def}}}}{{=}}}\\{\theta\mid x\in\varphi_{\theta}\\}\hskip
30.00005pt\Theta^{-}_{x}\mathrel{\stackrel{{\scriptstyle\makebox[0.0pt]{\mbox{\tiny
def}}}}{{=}}}{[0,1]}^{d}\setminus\Theta^{+},$ (5)

called a _monotone bi-partition_. With this perspective, membership is
entirely determined by whether or not the underlying concept’s parameter,
$\theta$, is in the accepting set,

$x\in\varphi_{\theta}\iff\theta\in\Theta^{+}.$ (6)

min distance
---

max travel time
---

x
---

path to boundary
---

$\Theta^{+}_{x}$
---
$\theta$
---

Figure 5: Mapping Ex. 8 to geometric perspective of concept class.

######  Example 9.

For instance, scaling and reflecting the parameters,
$\theta=\left(\frac{\tau}{T},\frac{D-d}{D}\right)$, yields a monotone
parametric family. Fig 5 illustrates. In particular, the ego (white) car wants
to go to the yellow region within some time budget, while maintaining a
minimum distance to the red parked car. This gets mapped to a bi-partition in
the normalized parameter space.

##### Thresholded rewards

Monotone predicate families include task specifications as thresholded rewards
to weighted sums over multi-dimensional rewards. In particular, let
$\vec{f}(i)\in{[0,1]}^{d}$ be a sequence feature vector for $i\in[1,N]$, for
$N\in\mathbb{N}$. Thresholded sums of linear rewards on these feature vectors
can be cast as a $d+1$ dimensional monotone predicate family. In particular,
let the thresholded sums be defined as $\sum_{i=1}^{N}w\cdot f(i)>\delta$ for
$w\in{[-1,1]}^{d},\delta\in[-d,d]$. We may define $\theta$ using:

$\theta_{j}=\begin{cases}(1-w_{j})/2&\text{if }j\leq d\\\
(\nicefrac{{\delta}}{{d}}+1)/2&\text{if }j=d+1\end{cases}.$ (7)

######  Remark.

If the $\mathcal{C}(x,y)$ is total, one derives a (noiseless) variant of the
learning setting considered in (Xu et al., 2020).

###  C Proof sketch for Proposition 2.4

###### Sketch.

Under exp4, a series of unproductive preference queries, i.e., ones that do
not change $\Phi^{X}$, will exponentially increase the weight of the
historical expert. Similarly, the historical expert will exponentially
increase the weight of the distinguishing membership query arm. Finally,
because the per round loss is bounded, there exist a lower bound on asking
distinguishing membership query. By Prop 2.4 the algorithm almost surely
requires finite queries. ∎

###  D Handling Error

Our concept learning algorithm can be adapted to gracefully handle two kinds
of labeling errors: (i) _Preorder violations_ and (ii) _MemRep violations_. A
preorder violation occurs when the underlying order relation is observed to
not be transitive or reflexive. This can be visualized using a Hasse Diagram
where such a violation would either correspond to a cycle or an inconsistency
in the node equivalence classes. Similarly, a MemReP violation occurs when the
Hasse diagram contains an edge, $(x,y)$, where $x\prec y$, but
$x\in\varphi^{*}$ and $y\notin\varphi^{*}$.

Both classes of violations are easy to detect and isolate. In an explicit
Hasse diagram representation, a topological pass over the graph suffices. In
the case of SAT based concept classes, e.g., our DFA learning experiment in
Section 4, we simply analyze the UNSAT-core to determine which queries must be
dropped to find a consistent hypothesis. In either setting, one can alert the
user, allowing the violating query responses to be dropped or corrected before
resuming the learning algorithm. Combining with a final conformance tester
which asks additional redundant queries from a test distribution, yields a
probably approximately correct concept (Kearns & Vazirani, 1994).

###  E Learning DFAs: Additional Details and Results

####  E.1 Tomita Languages

The Tomita languages (Tomita, 1982) are a standard set of regular languages
and DFAs frequently used as a benchmark in DFA learning and identification.
The seven languages have a number of appealing qualities: they are relatively
parsimonious, and they collectively span a number of interesting properties,
including distributions of accepting and rejecting strings, existence of sink
states, and relative ease of identification with a small number of membership
queries.

For the Tomita languages, we used a manually designed preference ordering to
incoporate more semantic meaning into the ordering and thereby encourage
better learning from preference queries themselves. The preference ordering
works as follows: Positively labeled atoms are still always preferred over
negatively labeled atoms, as expected. When comparing two negatively labeled
atom, the atom that took longer to reach a sink state (i.e., a rejecting state
that cannot be transitioned out from) in the DFA was preferred, if a sink
state existed. If neither atom reached a sink state, the atom with a longer
accepting prefix was preferred. When comparing two positive atoms, we
enumerate the four possible two-token extensions to the atoms and prefer the
atom that is more frequently accepted when considering all of the extensions.

In Tables 1, 2, and 3, we show the results for the Tomita languages experiment
for our MemRePs algorithm and the membership query-only baseline (where the
cost for asking a preference query is set to $\infty$), averaged across 20
trials. Note that we omit the comparison between the number of equivalence
queries asked by each method since these numbers were the same for both.
Overall, we notice that the tradeoff between membership and preference queries
is apparent as the relative cost between the two increases. However, this
tradeoff is more pronounced in some languages (languages #4, 5, and 7) than
other (languages #1, 2, and 6). An example language (language #5) is further
illustrated in

We also note that the number of preference queries needed in some cases, such
as in languages 4 and 7, dramatically increase with the increased cost ratio.
The high variance for preference queries needed also indicates that the
combination of the CMAB algorithm and atom selection process leaves room for
improvement and consistency.

| DFA 1 | DFA 2 | DFA 3 | DFA 4 | DFA 5 | DFA 6 | DFA 7
---|---|---|---|---|---|---|---
| Ours | Base | Ours | Base | Ours | Base | Ours | Base | Ours | Base | Ours | Base | Ours | Base
Cost=1 | 3.1 | 3.6 | 6.6 | 7.0 | 5.1 | 7.3 | 12.5 | 16.6 | 8.4 | 11.4 | 5.7 | 6.7 | 17.3 | 18.7
Cost=2 | 3.1 | 3.6 | 6.2 | 7.0 | 4.7 | 7.3 | 11.2 | 16.6 | 6.6 | 11.4 | 5.5 | 6.7 | 16.1 | 18.7
Cost=4 | 3.0 | 3.6 | 5.3 | 7.0 | 3.8 | 7.3 | 11.4 | 16.6 | 5.6 | 11.4 | 5.5 | 6.7 | 14.9 | 18.7
Cost=8 | 3.0 | 3.6 | 3.5 | 7.0 | 2.7 | 7.3 | 6.8 | 16.6 | 4.2 | 11.4 | 5.4 | 6.7 | 12.2 | 18.7
Table 1: Mean number of membership queries asked by our membership-and-preference selection algorithm (Ours) in comparison to the membership-only baseline (Base) on the seven Tomita DFAs. Little to no difference is seen in the simpler DFAs, whereas the discrepancy in query amount is more pronounced in more complicated DFAs. | DFA 1 | DFA 2 | DFA 3 | DFA 4 | DFA 5 | DFA 6 | DFA 7
---|---|---|---|---|---|---|---
| Ours | Base | Ours | Base | Ours | Base | Ours | Base | Ours | Base | Ours | Base | Ours | Base
Cost=1 | 0.13 | 0.23 | 0.74 | 0 | 0.66 | 0.49 | 1.57 | 1.61 | 1.28 | 1.01 | 0.67 | 0.50 | 2.00 | 1.78
Cost=2 | 0.43 | 0.23 | 1.01 | 0 | 0.61 | 0.49 | 1.62 | 1.61 | 1.18 | 1.01 | 0.92 | 0.50 | 0.87 | 1.78
Cost=4 | 0.22 | 0.23 | 0.78 | 0 | 0.87 | 0.49 | 1.58 | 1.61 | 0.64 | 1.01 | 0.81 | 0.50 | 2.19 | 1.78
Cost=8 | 0.41 | 0.23 | 0.67 | 0 | 0.64 | 0.49 | 0.97 | 1.61 | 1.10 | 1.01 | 0.49 | 0.50 | 1.30 | 1.78
Table 2: Variances for number of membership queries asked by our membership-and-preference selection algorithm in comparison to the membership-only baseline on the seven Tomita DFAs. | DFA 1 | DFA 2 | DFA 3 | DFA 4 | DFA 5 | DFA 6 | DFA 7
---|---|---|---|---|---|---|---
| Mean | Var. | Mean | Var. | Mean | Var. | Mean | Var. | Mean | Var. | Mean | Var. | Mean | Var.
Cost=1 | 1.4 | 0.75 | 4.7 | 1.11 | 4.6 | 2.72 | 10.5 | 6.42 | 5.1 | 2.14 | 3.3 | 1.10 | 11.5 | 4.18
Cost=2 | 2.6 | 0.88 | 5.2 | 0.92 | 5.0 | 1.66 | 25.1 | 11.1 | 7.0 | 1.76 | 3.3 | 2.28 | 22.0 | 9.27
Cost=4 | 3.1 | 0.79 | 6.3 | 0.83 | 9.7 | 2.05 | 41.3 | 12.71 | 8.1 | 2.95 | 3.7 | 1.44 | 44.3 | 8.22
Cost=8 | 3.8 | 0.83 | 8.1 | 0.77 | 15.9 | 2.28 | 84.3 | 17.23 | 9.1 | 5.11 | 4.1 | 1.34 | 78.7 | 16.65
Table 3: Mean and variance for number of preference queries asked by our
membership-and-preference selection algorithm on the seven Tomita DFAs.

Figure 6: Trade-off between preference queries and membership queries for
tomita language #5. The bars plotted show the contribution of membership (red,
bottom), preference (blue, middle), and equivalence (green, top) queries.

####  E.2 Robustness Experiment

As mentioned in the main text, we designed our algorithm to be robust in noisy
settings, where the response to a query is flipped to be incorrect some
proportion of the time. In our algorithm’s implementation for DFAs, if a
labeling error occurs that causes a violation, the UNSAT-core is extracted to
see which existing assumptions caused this violation, and those assumptions
are then dropped. We demonstrate the effect of labeling errors in an
experiment, where an example DFA (in this case, Tomita language #6) is learned
in settings of increasing proportions of labeling errors. The results are
displayed in figure 7, where an increasing rate of error causes more
assumptions that need to be dropped by our algorithm, resulting in more
queries required to learn the correct concept. In other words, as errors are
made more frequently and assumptions are discarded more often, it becomes
harder for the necessary set of assumptions to be efficiently obtained by the
learner.

Figure 7: Greater numbers of queries are required to learn the target DFA
(Tomita language #6) as the error rate increases. The bars plotted show the
contribution of membership (red, bottom), preference (blue, middle), and
equivalence (green, top) queries.

####  E.3 Scalability Experiments

To understand how our algorithm scales as our target DFA increases in
complexity, we evaluate our algorithm’s scalability on a simple one-symbol
language that determines whether the length of an input sequence is modulo
some positive integer $k$. The size of the DFA is $k$ states with a single
accepting state. We provide the results of our algorithm’s performance as $k$
increases in Table 4. Not included in the table is the number of equivalence
queries used in each DFA, which did not vary as a function of membership-to-
preference cost ratio. The mean number of equivalence queries asked were 6.4,
9.1, 9.9, and 22.6 for DFA states 5, 10, 20, and 40, respectively. The
equivalence queries in this setting were highly informative, allowing the
number of other query types to scale efficiently but somewhat restricting
those queries’ utility.

| 5 States | 10 States | 20 States | 40 States
---|---|---|---|---
| # Mem. | # Pref. | # Mem. | # Pref. | # Mem. | # Pref. | # Mem. | # Pref.
Cost=1 | 2.2 | 1.2 | 5.7 | 3.6 | 9.4 | 7.4 | 18.7 | 7.8
Cost=2 | 2.0 | 1.5 | 4.7 | 5.6 | 8.1 | 8.4 | 17.9 | 9.9
Cost=4 | 1.4 | 2.6 | 4.6 | 6.6 | 6.2 | 12.2 | 15.4 | 19.5
Cost=8 | 1.0 | 2.9 | 3.9 | 10.9 | 3.7 | 17.8 | 11.3 | 31.4
Table 4: Number of Membership and Preference Queries for the scaled modulo DFA
structure, averaged over ten trials.

In addition to the previous experiment, we generalized Tomita Language #4,
which originally is defined as a 3-state DFA that encodes the task “any string
without more than 2 consecutive ‘0’s”, to any string with more than $n$
consecutive ‘0’s. The size of the DFA in states is $n+2$, including the
rejecting sink state. We vary $n$ from 1 to 4 and present our results in Table
5. We note that the number of queries required quickly increases with the
increase in number of states, which is to be expected given the super-linear
increase in search space size with number of states.

| 3 States | 4 States | 5 States | 6 States
---|---|---|---|---
| # Mem. | # Pref. | # Mem. | # Pref. | # Mem. | # Pref. | # Mem. | # Pref.
Cost=1 | 7.3 | 3.1 | 12.5 | 10.5 | 23.3 | 14.3 | 32.4 | 34.6
Cost=2 | 6.5 | 6.3 | 11.2 | 25.1 | 20.3 | 26.9 | 28.6 | 59.0
Cost=4 | 5.6 | 17.7 | 11.4 | 41.3 | 19.1 | 71.7 | 25.8 | 143.6
Cost=8 | 5.1 | 34.1 | 6.8 | 84.3 | 17.9 | 147.2 | 23.6 | 218.6
Table 5: Number of Membership and Preference Queries for the scaled Tomita #4
experiment, averaged over ten trials. The number of equivalence queries
remained constant over costs.


# Investigating Fouling Efficiency in Football
Using Expected Booking (xB) Model

Adnan Azmat
School of Computer Science and Engineering
Nanyang Technological University, Singapore
<EMAIL_ADDRESS>Su Su Yi
School of Computer Science and Engineering
Nanyang Technological University, Singapore
<EMAIL_ADDRESS>
###### Abstract

This paper introduces the Expected Booking (xB) model, a novel metric designed
to estimate the likelihood of a foul resulting in a yellow card in football.
Through three iterative experiments, employing ensemble methods, the model
demonstrates improved performance with additional features and an expanded
dataset. Analysis of FIFA World Cup 2022 data validates the model’s efficacy
in providing insights into team and player fouling tactics, aligning with
actual defensive performance. The xB model addresses a gap in fouling
efficiency examination, emphasizing defensive strategies which often
overlooked. Further enhancements are suggested through the incorporation of
comprehensive data and spatial features.

##  1 INTRODUCTION

In the realm of football, every decision made on the field can significantly
influence the game’s outcome. Among these decisions, fouls and their
subsequent consequences are often overlooked, despite their pivotal role in
the game. Current methodologies primarily focus on offensive actions leading
to goals, leaving the subtler yet equally crucial defensive aspect under-
emphasized. Analyzing defensive play poses inherent challenges, and football
discussions often prioritize offensive actions, thereby overshadowing the
importance of defensive contributions.

###  1.1 Problem Statement

In this paper, we introduce a new metric, the Expected Booking (xB) model.
This model is designed to estimate the likelihood of a player receiving a
yellow card if/for a foul committed at a specific moment during a match. Our
focus is primarily on yellow cards due to their relative ambiguity and higher
frequency of issuance compared to red cards. Red cards, which are issued less
frequently, have clear rules for issuance. On average, yellow cards are issued
18 times more frequently than red cards [4].

Our attention is more specifically directed towards non-dangerous fouls,
excluding those resulting from bad behavior. We believe that non-dangerous
fouls, excluding those resulting from bad behavior, truly represent the
tactical aspect of fouls and do not involve impulsive decisions by players
that easily lead to bookings.

We anticipate that the cumulative Expected Booking probability can be used to
rate the fouling ability of teams and players over individual matches or
seasons, similar to how expected goals are used to rate scoring abilities.
This approach offers a comprehensive view of the game, highlighting both
offensive and defensive contributions. It also provides an opportunity to
study the differences in refereeing decisions across various leagues and
combinations.

###  1.2 Motivation

Most efforts in football analysis have been predominantly focused on aspects
such as attacking, scoring, and passing. While statistics for offensive plays
like goals scored, expected goals, assists, expected assists, dribbles, key
passes, pass accuracy, and chances created are readily available and
comprehensive, the metrics for defensive actions often lack depth and detail.

Defensive actions are typically represented by basic statistics like fouls,
bookings (yellow cards, red cards), tackles, interceptions, and clearances.
However, these metrics do not fully capture the complexity and strategic
importance of defensive plays in a football match. This is the motivation
behind the Expected Booking (xB) model.

Inspired by the Expected Goals model, which provides a measure of a striker’s
performance relative to the opportunities they had, we aim to develop a
similar model for defensive actions. To the best of our knowledge, there has
been no prior research or study conducted on or related to the Expected
Booking model. We believe that our research has the potential to offer
valuable insights and contributions to the subject matter.

###  1.3 Related Work

Expected Goals (xG) Model. Rathke, A. 2017 examined goal scoring in European
football leagues and factors which are associated with predicting Expected
Goals (xG) [5]. He analysed the factors, distance of the shot taken from goal
and the angle of the shot in relation to the goal and used Expected Goals
Method (xG) to calculate the chances a team has to score and concede goals
[5]. xG models use statistical and machine learning techniques to predict the
probability of a shot resulting in a goal. These models often consider various
features such as shot location, angle, and player positions.

VAEP Framework. T Decroos et al., 2019 proposed VAEP (Valuing Actions by
Estimating Probabilities) framework for valuing actions performed by soccer
players [3]. The VAEP framework provides a simple approach to valuing actions
that is independent of the representation used to describe the actions [3]. It
considers all types of actions (e.g., passes, crosses, dribbles, take-ons, and
shots) and accounts for the circumstances under which each of these actions
happened as well as their possible longer-term effects [3].

Expected Threat (xT) Model . K Singh introduced xT (Expected Threat) model for
team behaviour in possession to gain a deeper understanding of buildup play
[6]. K Singh proposed that each action should be assigned a score in
isolation, disregarding what happened before and after it in the possession
[6]. One simplified way of viewing buildup play is as follows: when a team has
possession in a certain position, they can either shoot (and score with some
probability), or move the ball to a different location via a pass or a dribble
[6]. This continues until the team either loses possession, or scores a goal
[6]. xT model assigns a score to each player action (pass or dribble) based on
how much it contributed to the buildup play [6]. The point of xT is to come up
with a metric that can quantify threat at any location on the pitch [6].

##  2 DATA and FRAMEWORKS

The data used in our research is primarily sourced from StatsBomb [1], which
provides event data and 360 data. Football event data is a collection of
detailed information about every event that occur during a football match. The
data includes information about the location of the ball, the players’
movements, and the actions they take, such as passes, shots, and tackles. The
data also includes information about the outcome of each event, such as
whether a pass was successful or not.

###  2.1 StatsBomb Event Data

StatsBomb event data is renowned for its detail and accuracy. It records over
3,400 events per match, providing a comprehensive view of each game. This data
includes unique features that allow for deeper analysis.

###  2.2 StatsBomb 360 Data

StatsBomb 360 is an extension to the football event data. It adds player
locations to the event data, providing a more contextual view of the game.
This data is collected using a hybrid of computer vision and manual oversight,
ensuring its accuracy and reliability. However, it is important to note that
the availability of open-source 360 data is significantly less compared to
event data.

###  2.3 Socceraction

In addition to StatsBomb data, we also use Socceraction [2], a Python package
for objectively quantifying the impact of individual actions performed by
soccer players using event stream data. The general idea is to assign a value
to each on-the-ball action based on the action’s impact on the game outcome,
while accounting for the context in which the action happened. This allows us
to measure the effectiveness of each player’s actions in a game.

##  3 FEATURES and LABELS

We filter the event data specifically for fouling events. After the data pre-
processing and preparation steps, each instance in our training data
represents a non-dangerous foul event, which is not a result of bad behavior.
Non-dangerous fouls are identified by excluding fouls due to handball,
dangerous play, foul out, dive, 6 seconds, and backpass pick.

###  3.1 Features

In developing the Expected Booking (xB) model, we leveraged our football
domain knowledge and employed statistical methods to identify key features for
the model. For the purpose of this analysis, the team of the fouled player is
referred to as the team in possession, and the fouling player’s team is
referred to as the defending team.

####  3.1.1 Minutes

This feature represents the exact minute during the match when the foul was
committed. It provides context about the stage of the game, which can
influence the likelihood of a booking.

####  3.1.2 Distance to Goal

This feature measures the distance from the location of the foul event to the
goal of the team in possession. This feature is represented by the black
dotted line in figure 2.

####  3.1.3 Angle to Goal

This feature calculates the angle from the location of the foul event to the
midpoint of the defending team’s goal. This feature is represented by the pink
arc in figure 2.

####  3.1.4 Foul Count Player

This feature counts the number of fouls committed by the fouling player in the
current match up to the time of the current foul. It serves as an indicator of
the player’s overall aggression or recklessness within the specific game.

####  3.1.5 Foul Count Team

This feature counts the number of fouls committed by the defending team in the
current match up to the time of the current foul. It provides insight into the
team’s overall defensive strategy and discipline within the specific game.

####  3.1.6 Goal Difference

This feature calculates the goal difference between the team in possession and
the defending team at the time of the foul. It can provide context about the
competitive dynamics of the match.

####  3.1.7 VAEP Offensive

VAEP (Valuing Actions by Estimating Probabilities) is a framework for valuing
actions performed by players [3]. VAEP value of an action is the sum of
action’s offensive value and defensive value [3]. It is given by the equation:
$V(a_{i},x)=\Delta P_{\text{scores}}(a_{i},x)+(-\Delta
P_{\text{concedes}}(a_{i},x))$.

Figure 1: VAEP values for each action in a sequence of plays

VAEP offensive is denoted by $P_{scores}$. This feature captures the offensive
threat posed by the team in possession [3]. The rationale is that the
defending team is more likely to receive a card if the team in possession
poses a significant offensive threat [3].

####  3.1.8 Features from 360 data

We utilize the comprehensive StatsBomb 360 data to provide additional context
to the game. Although the 360 data does not include the coordinates of all
players on the field, it does provide a ‘freeze frames’ column which contains
the coordinates of all players visible in the camera frame at the time of the
foul.

A. Attackers Count

This feature counts the number of players from the team in possession who are
located ahead of the foul location. It provides insight into the attacking
formation and strategy of the team in possession. This feature is represented
by the red numberings: 1 and 2 in figure 2.

B. Defenders Count

This feature counts the number of players from the defending team who are
positioned between the foul location and their own goal. It provides insight
into the defensive formation and strategy of the defending team. This feature
is represented by the blue numberings: 1, 2 and 3 in figure 2.

Figure 2: Dummy instance to show feature values

###  3.2 Classification Labels

Our classification task involves binary outcomes, transforming it into a
binary classification problem. Each feature sample is associated with one of
two possibilities: either receiving a yellow card or not.

However, it’s worth noting that even though this is a binary classification
task, we can additionally estimate probability of a booking (yellow card) for
any given data instance. The cumulative probability of individual foul events
offers insights into player behavior, team dynamics, and competition trends,
enhancing our understanding of booking incidents.

##  4 EXPERIMENT

We conducted three iterations of experiments utilizing StatsBomb event and 360
data from various competitions.

###  4.1 Naive Exploration: Preliminary Findings

We leverage the limited 360 dataset comprising 957 foul events from 4
competitions and 210 matches, encompassing six features: minutes, score
difference, distance to goal, angle to goal, foul count player and foul count
team. The dataset is then partitioned into training and testing sets,
following an 80-20 split. We proceed to train the model using two traditional
classifiers, namely Decision Tree and Logistic Regression, alongside two
ensemble classifiers—Gradient Boosting and XGBoost, ensuring a comprehensive
exploration of diverse modeling techniques.

|  | Decision
---
Tree
| Logistic
---
Regression
| Gradient
---
Boosting
XGBoost
Accuracy | 0.55 | 0.57 | 0.58 | 0.59
Precision | 0.45 | 0.42 | 0.47 | 0.50
Recall | 0.50 | 0.16 | 0.32 | 0.47
F1-Score | 0.47 | 0.23 | 0.38 | 0.48
| ROC AUC
---
Score
0.59 | 0.56 | 0.59 | 0.61
Table 1: Test data results from different classifiers Figure 3: ROC Curve from
Different Classifiers

Table 1. and Figure 3. showing the classification results of two traditional
classifiers and two ensemble classifiers. Overall, the ensemble methods
outperform traditional classifiers. Consequently, we opt to employ the
ensemble models for the next experiments.

###  4.2 Including Possession Values and Spatial Data

For this experiment, we introduced three more features, namely vaep offensive
and 360 features: teammate count and opponent count to enrich our small
dataset of 957 instances. Following an 80-20 split for training and testing
samples, we compared classification results of the two models which is shown
in table 2 and figure 4.

|  | Gradient Boosting
---
XGBoost
Accuracy | 0.76 | 0.79
Precision | 0.65 | 0.71
Recall | 0.76 | 0.75
F1-Score | 0.70 | 0.73
ROC AUC Score | 0.82 | 0.84
Table 2: Test set results from two ensemble classifier with additional features Figure 4: ROC Curve from Gradient Boosting & XGBoost Competition Name | Season Name | Total Matches | Fouls Committed | Teams Count | Players Count
---|---|---|---|---|---
Serie A | 2015/2016 | 380 | 2716 | 20 | 446
Premier League | 2015/2016 | 380 | 2418 | 20 | 402
La Liga | 2015/2016 | 380 | 3388 | 20 | 452
Ligue 1 | 2015/2016 | 376 | 2321 | 20 | 424
Bundesliga | 2015/2016 | 304 | 2013 | 18 | 370
Indian Super league | 2021/2022 | 114 | 619 | 11 | 195
FIFA World Cup | 2018 | 64 | 385 | 32 | 246
FIFA World Cup | 2022 | 64 | 370 | 32 | 253
UEFA Euro | 2020 | 51 | 329 | 24 | 207
Table 3: Training data for the experiment 4.3. [Fouls committed count is after
filtering]

We observe a significant improvement in outcomes in terms of accuracy,
precision, recall, F1-score, and ROC AUC score following the inclusion of
three pivotal features into the dataset. Notably, the accuracy demonstrates an
impressive surge of 20%, while the ROC AUC score experiences a substantial
increase of 23% with XGBoost classifier.

###  4.3 Exceptional Performance with Significant Data

The publicly available 360 data by StatsBomb covers only 4 competitions and
210 number of matches. Apart from the 360 data, we try to leverage the large
amount of traditional event data by StatsBomb hoping to improve our model by
using a larger sample space but sacrificing the context provided by the 360
features.

The data used for training the model include all of publicly released men’s
event data by StatsBomb at the writing of this paper. Table 3 shows data used
to train the model. Apart from this there were few more matches in the
StatsBomb data which we utilized for training. We trained the model on a total
of 2690 matches with approx 20000 foul events.

Metric | Value
---|---
Accuracy | 0.83
Precision | 0.83
Recall | 0.78
F1-Score | 0.82
ROC AUC Score | 0.91
Table 4: XGBoost Metrics Figure 5: ROC Curve for Experiment 4.3 Figure 6:
Confusion Matrix for Experiment 4.3

In this experiment, we aimed to boost model performance by leveraging a
substantial amount of traditional event data from StatsBomb, complementing the
limited 360 data coverage. The expanded dataset showcased remarkable results
for the XGBoost classifier. With an accuracy of 83%, precision of 83%, recall
of 78%, F1-score of 82%, and an impressive ROC AUC score of 91%, this
experiment underscores the effectiveness of utilizing a larger sample space.

##  5 ANALYSIS

Utilizing the cumulative Expected Booking probability, we can effectively
visualize player and team statistics. This section showcases the efficacy of
our model by applying it to the FIFA World Cup 2022 data, and presenting the
results through comprehensive tables and visualizations. These graphical
representations aid in the identification of teams’ fouling tactics.

###  5.1 FIFA World Cup 2022: Team Statistics

A. Expected Booking (per match) vs Actual Bookings (per match)

The y-axis represents the sum of Expected Booking (xB), which is the
cumulative probability of receiving a yellow card, divided by the total
matches played by the team. The x-axis, on the other hand, represents the sum
of actual yellow cards received, divided by the total matches played by the
team.

Figure 7: FIFA World Cup 2022 (Yellow card cumulative probability vs Actual
yellow card per match)

B. Ratio (xB/B) vs Fouls per Match

The y-axis in this case represents the ratio of the cumulative yellow card
probability (xB) to the actual number of yellow cards (B) received. Here, xB
stands for expected booking and B stands for actual bookings. A higher ratio
indicates a better fouling value. The x-axis represents the number of fouls
per match, excluding those that are non-dangerous and not due to bad
behaviour.

Figure 8: FIFA World Cup 2022 (Ratio vs Fouls per match)

Our analysis reveals that Morocco demonstrated exceptional fouling tactics.
They committed more fouls on average in each match, and also successfully
avoided yellow cards, as indicated by their high ratio of cumulative yellow
card probability to the actual number of yellow cards received.

###  5.2 FIFA World Cup 2022: Player Statistics

The following plot is generated for players who played a total of at least 90
minutes during the world cup.

A. Ratio (xB/B) vs Fouls per 90

Figure 9: FIFA World Cup 2022 (Ratio vs Fouls per match)

B. Expected Booking: Best Statistics

Player | xB | B | Ratio
---|---|---|---
Marcos Javier Acuña | 3.78 | 3 | 1.26
Woo-Young Jung | 2.42 | 2 | 1.21
Fabian Lukas Schär | 1.87 | 2 | 0.94
Nemanja Gudelj | 1.87 | 2 | 0.94
Matty Cash | 1.87 | 2 | 0.93
Jackson Irvine | 1.86 | 2 | 0.93
Miloš Degenek | 1.79 | 2 | 0.89
Ngoran Suiru Fai Collins | 1.77 | 2 | 0.89
Table 5: Statistics of players’ xB, B, and Ratio.

According to our model, Marcos Acuña, the Argentine defender, emerged as the
most strategic fouler during the FIFA World Cup 2022.

##  6 CONCLUSION

In this paper, we present a simple yet novel metric called the Expected
Booking (xB) model, designed to estimate the likelihood of a foul resulting in
a yellow card. Through three iterative experiments, the model, favoring
ensemble methods, exhibited performance improvements with the inclusion of
additional features and an expanded dataset. Notably, the analysis of FIFA
World Cup 2022 data, which aligns with actual defensive performance, validated
the model’s efficacy in providing concise insights into team and player
fouling tactics. This underscores its ability to provide valuable insights
into football events.

The xB model serves the purpose of addressing a notable gap in the examination
of fouling efficiency, shedding light on aspects of defensive strategies often
overlooked by prevalent football studies. We assert that further enhancements
in the xB model can be attained through the incorporation of more
comprehensive data and better spatial features using event freeze frames or
tracking data.

## References

  * [1] https://statsbomb.com/what-we-do/hub/free-data/.
  * [2] https://github.com/ML-KULeuven/socceraction.
  * [3] Tom Decroos, Lotte Bransen, Jan Van Haaren, and Jesse Davis.  Actions speak louder than goals: Valuing player actions in soccer.  In Proceedings of the 25th ACM SIGKDD international conference on knowledge discovery & data mining, pages 1851–1861, 2019.
  * [4] Raffaele Poli, Roger Besson, and Loïc Ravenel.  Global study of penalty cards in professional football.  2020\.
  * [5] Alex Rathke.  An examination of expected goals and shot efficiency in soccer.  Journal of Human Sport and Exercise, 12(2):514–529, 2017.
  * [6] Karun Singh.  Introducing expected threat (xt). 2019.