# Towards Efficient Active Learning of PDFA

F. Mayr S. Yovine F. Pan
Facultad de Ingeniería
Universidad ORT Uruguay
Montevideo, Uruguay
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>&N. Basset T. Dang
Verimag
Université Grenoble-Alpes
Grenoble, France
<EMAIL_ADDRESS>
<EMAIL_ADDRESS>
###### Abstract

We propose a new active learning algorithm for PDFA based on three main
aspects: a congruence over states which takes into account next-symbol
probability distributions, a quantization that copes with differences in
distributions, and an efficient tree-based data structure. Experiments showed
significant performance gains with respect to reference implementations.

_Keywords_ Active learning $\cdot$ PDFA $\cdot$ Quantization

##  1 Introduction

We are interested in the problem of efficiently learning probabilistic
deterministic finite automata (PDFA) in the context of the general active MAT-
learning framework proposed in [1] where a _learner_ and a so-called _minimum
adequate teacher_ interact by asking and responding questions, respectively.
The learner’s purpose is to unveil the hidden target automaton only known to
the teacher. The latter allows the former to ask two kinds of questions,
namely _membership_ ($\mathbf{MQ}$) and _equivalence_ ($\mathbf{EQ}$) queries.

$\mathbf{MQ}$ seeks to discover the automaton’s outcome for a particular
string. Originally, the purpose of $\mathbf{MQ}$ is to know whether a string
belongs to the language to be learnt or, equivalently, whether it is accepted
by the associated automaton. This name has been kept in later applications to
other classes of automata. In [3, 2], the framework is used to prove
learnability of multiplicity automata which compute functions mapping strings
to elements of a _field_. In this case, the name $\mathbf{MQ}$ is retained
even when the answer is the value of the computed function, which may not be
Boolean. The same approach is followed in [15] where $\mathbf{MQ}$ is used to
refer to the function that returns the probability of the last symbol in a
string.

$\mathbf{EQ}$ provides means for determining to what extent the hypothesis
automaton produced by the learner approximates the target one. In the case of
_exact_ learning, this query checks whether they both produce the same outcome
to $\mathbf{MQ}$ for all strings. When $\mathbf{MQ}$ are not binary, such as
for PDFA, it could be useful to relax equality in order to learn _similar_
hypotheses that tolerate small discrepancies. For instance, in [5, 15, 12]
equality is replaced by a _similarity_ relation. However, that similarity
relation is not an equivalence as it lacks transitivity.

In the context of DFA, it is known that using appropriate data structures,
such as trees, and efficiently processing counterexamples lead to significant
gains in terms of computation time [10, 8]. To the best of our knowledge,
these approaches have not yet been explored for active learning of PDFA. The
algorithms proposed in [9, 2] rely on $\mathbf{MQ}$ that compute the
probability of a string and on an observation table to store the results. In
[14], $\mathbf{MQ}$ return state distributions, that is, the probability that
the target probabilistic automaton enters a state after reading an input
string. This requires knowing the number of states of the target in advance.
These works focused on theoretical results without implementations of them
being publicly available. In [7], learning PDFA is a building block of an
assume-guarantee framework for verification of probabilistic systems.
$\mathbf{MQ}$ asks for the probability of accepting a string and results are
stored in an observation table. However, the overall goal is not to learn a
PDFA equivalent to a hidden target but only an appropriate assumption for
doing a compositional proof of correctness. To achieve this, the algorithm
uses an $\mathbf{EQ}$ that relies on language inclusion of PDFA and
probabilistic model-checking. All these works rely on exact equality of
$\mathbf{MQ}$ outcomes. To deal with noise in distributions,
$\mathrm{WL}^{\ast}$ [15] proposes a non-equivalence similarity relation
between probability distributions and develops an algorithm to learn similar
hypotheses according to it. Note that $\mathrm{WL}^{\ast}$ uses clustering to
group responses to $\mathbf{MQ}$ stored in the table.

Based on these observations, we formulate a learning framework for PDFA where
the teacher’s answers to $\mathbf{MQ}$ are probability distributions over the
symbols a string could be continued with. These are called _next-symbol_
probability distributions. Besides, in the case the learner is allowed to
produce hypotheses whose next-symbol probability distributions are
approximations of the target ones, we propose to resort to quantization as an
abstraction which allows us to define a coarser equivalence relation than the
latter. This ensures the learnt automaton to be equivalent to the target one
modulo this relation. Finally, we propose and implement $\mathrm{QuaNT}$, a
learning algorithm for PDFA that uses an adaptation of the tree structure of
[10]. In order to assess its performance, we compared $\mathrm{QuaNT}$ to a
clustering-based algorithm that uses an observation table and a tolerance-
based non-equivalence similarity relation, similar to $\mathrm{WL}^{\ast}$.
The experiments carried out showed that $\mathrm{QuaNT}$ was orders of
magnitude more efficient.

The paper is organized as follows. Section 2 gives core definitions and
results of interest. Section 3 presents our PDFA learning algorithm
$\mathrm{QuaNT}$. Section 4 discusses experimental results. Section 5
summarizes the contributions.

##  2 PDFA

Let $\Sigma$ be a finite _alphabet_ and $\Sigma_{\$}$ to be the set
$\Sigma\cup\\{\$\\}$, where $\$$ is a special _terminal_ symbol not in
$\Sigma$. $\Delta(\Sigma_{\$})$ is probability simplex over $\Sigma_{\$}$. A
PDFA $A$ over $\Sigma$ is a tuple $(Q,q_{\mathrm{in}},\pi,\tau)$, where $Q$ is
a finite set of _states_ , $q_{\mathrm{in}}\in Q$ is an _initial_ state,
$\pi:Q\rightarrow\Delta(\Sigma_{\$})$ associates a probability distribution
over $\Sigma_{\$}$ to each state, and $\tau:Q\times\Sigma\rightarrow Q$ is the
_transition_ (total) function. Fig. 1($a$-$b$) depicts an example. Let $P_{q}$
be the probability distribution over $\Sigma^{\ast}$, such that $P_{q}=P(s|q)$
is the probability of $s\in\Sigma^{\ast}$ from state $q\in Q$, defined as:

$\displaystyle P(\lambda|q)=\pi(q)(\$),\lambda\textit{ is the empty string,}$
$\displaystyle\quad P(\sigma s|q)=\pi(q)(\sigma)\cdot
P(s|\tau(q,\sigma)),\sigma\in\Sigma,s\in\Sigma^{\ast}$

A PDFA $A$ computes a function $f_{A}$ from $\Sigma^{\ast}$ to $[0,1]$. For
any string $s\in\Sigma^{\ast}$, $f_{A}(s)=P_{q_{\mathrm{in}}}(s)$. For
instance, the PDFA in Fig. 1 maps the empty string $\lambda$ to 0 and every
string $a^{n}$, $n\geq 1$, to $0.5^{n}$. We define $\tau^{\ast}(q,s)$ to be
the natural extension of $\tau$ to strings, that is, the state reached by $A$
when going through $s$ starting at state $q$:

$\displaystyle\tau^{\ast}(q,\lambda)=q$
$\displaystyle\qquad\tau^{\ast}(q,\sigma s)=\tau^{\ast}(\tau(q,\sigma),s)$

Similarly, we define $\pi^{\ast}(s|q)$ to be the probability distribution of
the state reached by $A$ when going through $s$ from state $q$:

$\displaystyle\pi^{\ast}(s|q)$ $\displaystyle=\pi(\tau^{\ast}(q,s))$

We denote by $\tau^{\ast}(s)$ and $\pi^{\ast}(s)$ the state reached when going
through $s$ from the initial state $q_{\mathrm{in}}$ and the associated
distribution, respectively.

###  2.1 State equivalence

We define the relation $\equiv$ as follows: for every $q,q^{\prime}\in Q$,
$q\equiv q^{\prime}$ if for every $s\in\equiv$,
$\pi^{\ast}(s|q)=\pi^{\ast}(s|q^{\prime})$. Clearly, $\equiv$ is an
equivalence relation between states.

######  Proposition 1.

$\forall q_{1}\equiv q_{2}\in Q$, 1) $\pi(q_{1})=\pi(q_{2})$, and 2)
$\forall\sigma\in\Sigma,\tau(q_{1},\sigma)\equiv\tau(q_{2},\sigma)$. That is,
$\equiv$ is a congruence.

It follows that $\equiv$ induces a _quotient_ PDFA
$A{/_{\scriptscriptstyle\equiv}}=(Q{/_{\scriptscriptstyle\equiv}},\left[q_{\mathrm{in}}\right],\pi{/_{\scriptscriptstyle\equiv}},\tau{/_{\scriptscriptstyle\equiv}})$,
where $Q{/_{\scriptscriptstyle\equiv}}$ is the set of equivalence classes,
$\left[q\right]\in Q{/_{\scriptscriptstyle\equiv}}$ denotes the class of $q\in
Q$, and for any $q\in Q$, the probability distribution is
$\pi{/_{\scriptscriptstyle\equiv}}(\left[q\right])=\pi(q)$, and the transition
function is
$\tau{/_{\scriptscriptstyle\equiv}}(\left[q\right],\sigma)=\left[\tau(q,\sigma)\right]$
for any $\sigma\in\Sigma$. 111This quotient is different from [13] defined by
a partition resulting from merging states according to a compatibility
criterion which is not an equivalence relation.

######  Proposition 2.

For every PDFA $A$, $A{/_{\scriptscriptstyle\equiv}}$ computes the same
function as $A$.

Therefore, $\equiv$ can be extended to PDFA. For every PDFA $A$ and $B$,
$A\equiv B$ if their respective initial states $q_{\mathrm{in}}^{A}$ and
$q_{\mathrm{in}}^{B}$ are equivalent, that is, $q_{\mathrm{in}}^{A}\equiv
q_{\mathrm{in}}^{B}$.

######  Corollary 1.

$A\equiv B$ implies $f_{A}=f_{B}$. The converse does not hold in general.

###  2.2 Minimality

A PDFA is _minimal_ if any other PDFA that computes the same function has no
less states [2]. The simple PDFA in Fig. 1 is minimal since clearly the
function cannot be computed by a PDFA with a single state. Based on $\equiv$
we define a weaker notion of minimality as follows. A PDFA $A$ is said to be
_weakly minimal_ if for every $q,q^{\prime}\in Q$, $q\not\equiv q^{\prime}$.By
definition, for every PDFA $A$, $A{/_{\scriptscriptstyle\equiv}}$ is weakly
minimal.

######  Proposition 3.

Every minimal PDFA $A$ is also weakly minimal. The converse does not hold in
general.

An example of Proposition 3 is the PDFA in Fig. 1. However, the converse is
not true, that is, there are weakly minimal PDFA which are not minimal.
Consider for instance PDFA $A$ and $B$ in Fig. 2. We have that
$f_{B}((ab)^{n+1})=(0.1\cdot 0.2)(0.2\cdot 0.1)^{n}\cdot 0.3=(0.1\cdot
0.2)^{n+1}\cdot 0.3=f_{A}((ab)^{n+1})$, for $n\geq 0$. For any other string
$s\neq(ab)^{n+1}$, $f_{A}(s)=f_{B}(s)=0$. Hence, $A$ and $B$ compute the same
function. Moreover, they are both weakly minimal because
$\pi^{\ast}(\lambda|q)\neq\pi^{\ast}(\lambda|q^{\prime})$ for every pair of
states $q,q^{\prime}\in Q$, for each one of the automata, respectively. But
$B$ is certainly not minimal because it has more states than $A$. This example
also shows that $f_{A}=f_{B}$ does not entail $A\equiv B$.

###  2.3 Similarity of distributions

The equivalence defined above is not robust in the sense that two states whose
probability distributions differ very slightly are not equivalent. Consider
the PDFA $A_{\varepsilon}$ (c) in Fig. 1, where $\varepsilon\in(0,0.5]$. It
maps every string $a^{n}$, $n\geq 1$, to
$(0.5-\varepsilon)^{n-1}(0.5+\varepsilon)$. This PDFA is not equivalent to
PDFA $A$ in Fig. 1. However, $f_{A_{\varepsilon}}$ tends to $f_{A}$ as
$\varepsilon$ tends to $0$. Moreover, $\pi(q^{\prime}_{1})$ tends to
$\pi(q_{1})$. Previous works have addressed this issue by introducing a
_tolerance_ parameter $t$. In [15], states are compared using the probability
of the last symbol of a non-empty string defined as:

$\displaystyle\pi^{\ell}_{q}(s\sigma)=\pi^{\ast}(s|q)(\sigma)$
$\displaystyle\;\mathrm{where}\;\sigma\in\Sigma_{\$},s\in\Sigma^{\ast},q\in Q$
(1)

It is said that $q,q^{\prime}$ are $t$-equal, for $t\in[0,1]$, denoted
$q\approx_{t}q^{\prime}$, if
$L_{\infty}(\pi^{\ell}_{q},\pi^{\ell}_{q^{\prime}})\leq t$ where
$L_{\infty}(v,v^{\prime})=\max_{x}|v(x)-v^{\prime}(x)|$. PDFA $A$ and $B$ are
$t$-equal, denoted $A\approx_{t}B$, if
$q_{\mathrm{in}}^{A}\approx_{t}q_{\mathrm{in}}^{B}$. However, this approach
does not lead to an equivalence relation between states. That is why, to cope
with small perturbations in probabilities while preserving equivalence between
states, we propose to resort to a quantization defined over $\pi^{\ast}$as
follows.

Let $\kappa\in\mathbb{N}$, $\kappa\geq 1$, be a _quantization_ parameter. For
$n\in\mathbb{N}$, $0\leq n<\kappa-1$, we define $I_{\kappa}^{n}$ to be the
left-closed right-open interval $\left[n\kappa^{-1},(n+1)\kappa^{-1}\right)$,
and for $n=\kappa-1$, the closed interval $\left[n\kappa^{-1},1\right]$. Now,
for every real number $x\in[0,1]$, we define
$\left<x\right>_{\kappa}=I_{\kappa}^{n}$ such that $x\in I_{\kappa}^{n}$. For
instance, for $\kappa=2$, we have the quantization $[0,0.5),[0.5,1]$. Two
numbers $x,y\in\mathbb{R}$ are $\kappa$-equivalent, denoted $x=_{\kappa}y$ if
$\left<x\right>_{\kappa}=\left<y\right>_{\kappa}$. This definition extends
naturally to $\Delta(\Sigma_{\$})$. We denote
$\left<\Delta(\Sigma_{\$})\right>_{\kappa}$ the partition of
$\Delta(\Sigma_{\$})$ induced by $\kappa$. For $\delta\in\Delta(\Sigma_{\$})$,
$\left<\delta\right>_{\kappa}$ is called the _quantization vector_ of
$\delta$. For example,
$\left<(0.1,0.3,0.6)\right>_{2}=(I^{0}_{2},I^{0}_{2},I^{1}_{2})$.

Being $=_{\kappa}$ an equivalence relation, we can define a quantized version
of $\equiv$ as follows: $q\equiv_{\kappa}q^{\prime}$ if for every
$s\in\Sigma^{\ast}$, $\pi^{\ast}(s|q)=_{\kappa}\pi^{\ast}(s|q^{\prime})$. This
induces a unique quotient over states
$Q{/_{\scriptscriptstyle\equiv_{\kappa}}}$. Moreover, $\equiv_{\kappa}$ can be
extended to PDFA: for every PDFA $A$ and $B$, $A\equiv_{\kappa}B$ if
$q_{\mathrm{in}}^{A}\equiv_{\kappa}q_{\mathrm{in}}^{B}$. This allows extending
the notion of weakly minimality defined over $\equiv$ to $\equiv_{\kappa}$:
$A$ is said to be $\kappa$-_weakly minimal_ if for every $q,q^{\prime}\in Q$,
$q\not\equiv_{\kappa}q^{\prime}$. However, unlike $\equiv$, its quantized
version $\equiv_{\kappa}$ does not induce a unique quotient PDFA because
$\pi{/_{\scriptscriptstyle\equiv_{\kappa}}}(\left[q\right]_{\kappa})$ can be
_any_ distribution in $\left<\pi(q)\right>_{\kappa}$. Therefore, we define
$A{/_{\scriptscriptstyle\equiv_{\kappa}}}=\\{B\mid
A\equiv_{\kappa}B\land|Q^{A}{/_{\scriptscriptstyle\equiv_{\kappa}}}|=|Q^{B}|\\}$,
that is, the set of $\kappa$-weakly minimal PDFA which are $\kappa$-equivalent
to $A$.

To illustrate quantization, consider the PDFA $A$ (a) and $A_{\varepsilon}$
(c) in Fig. 1. Suppose $\varepsilon\in(0,0.1)$. For $\kappa=5$, we have the
quantization $[0,0.2),\ldots,[0.8,1]$. Then,
$\left<\pi(q_{1})(a)\right>_{5}=I^{2}_{5}=[0.4,0.6)=\left<\pi(q^{\prime}_{1})(a)\right>_{5}$,
since $0.4<0.5-\varepsilon<0.5$, and
$\left<\pi(q_{1})(\$)\right>_{5}=I^{2}_{5}=[0.4,0.6)=\left<\pi(q^{\prime}_{1})(\$)\right>_{5}$,
since $0.5<0.5+\varepsilon<0.6$. Thus, we have that
$q_{i}\equiv_{5}q^{\prime}_{i}$. Hence, $A\equiv_{5}A_{\varepsilon}$.

######  Proposition 4.

For every $q,q^{\prime}$, if $q\equiv_{\kappa}q^{\prime}$ then
$q\approx_{\kappa^{-1}}q^{\prime}$.

##  3 PDFA Learning: QuaNT

$\mathrm{QuaNT}$ is a learning algorithm that constructs a PDFA by interacting
with a teacher which makes use of oracles $\mathbf{MQ}_{\mathrm{QuaNT}}$ and
$\mathbf{EQ}_{\mathrm{QuaNT}}$. It has three major differences with
$\mathrm{WL}^{\ast}$. First, $\mathbf{MQ}_{\mathrm{QuaNT}}$ returns the next-
symbol probability simplex of a string, that is
$\mathbf{MQ}_{\mathrm{QuaNT}}(s)=\pi^{\ast}(s)$ for $s\in\Sigma^{\ast}$; while
$\mathbf{MQ}_{\mathrm{WL}^{\ast}}(s)$ returns
$\pi^{\ell}_{q_{\mathrm{in}}}(s)$, where $\pi^{\ell}$ is defined in (1).
Second, it relies on quantization rather than on tolerance for comparing
probability distributions. Since our quantization method induces a congruence,
there is no need for clustering states. Third, along the lines of [10] and [8]
algorithms, $\mathrm{QuaNT}$ builds a _classification_ tree instead of a
table. Similarly to these algorithms, tree leafs are PDFA states identified by
so-called _access_ strings and inner nodes are _distinguishing_ suffixes.
Nevertheless, in $\mathrm{QuaNT}$ the tree is not binary but $n$-ary, where
$n$ is the number of different classes which $\Delta(\Sigma_{\$})$ is
partitioned into, and tree arcs and leafs are labelled with elements of
$\left<\Delta(\Sigma_{\$})\right>_{\kappa}$ and $\Delta(\Sigma_{\$})$,
respectively.

#### N-ary classification tree

Given $s\in\Sigma^{\ast}$, we denote $\left[s\right]_{\kappa}$ the class of
the state reached by traversing $s$ in the target PDFA $A$, i.e.,
$\left[\tau^{\ast}(s)\right]_{\kappa}$. Hereinafter, we omit the quantization
parameter $\kappa$ when clear from context. The tree $T_{Acc,Dis}$ maintains a
set $Acc$ of access strings and a set $Dis$ of distinguishing strings where
for every pair of distinct strings $s,s^{\prime}\in Acc$: (1)
$\left[s\right]\neq\left[s^{\prime}\right]$, (that is,
$\tau^{\ast}(s)\not\equiv_{\kappa}\tau^{\ast}(s^{\prime})$), and (2) $\exists
d\in Dis$ s.t. $\pi^{\ast}(sd)\neq_{\kappa}\pi^{\ast}(s^{\prime}d)$. The
distinguishing string that labels the root of the tree is always $\lambda$
which is also an access string, so that the initial state of the PDFA can be
accessed.

######  Proposition 5.

The number of leaves of $T$ is at most
$|Q{/_{\scriptscriptstyle\equiv_{\kappa}}}|$.

Fig. 3 (left) shows an example of $n$-ary classification tree. The
quantization parameter is $\kappa=10$. Tree leafs correspond to the states of
the PDFA shown on the right, identified with their associated access strings:
$Acc=\\{\lambda,0,1,10\\}$. Every leaf is labeled with a vector corresponding
to the probability distribution of the state, where the first element is the
probability of $\$$, the second element is the probability of $0$, and the
last element is the probability of $1$. For example:
$\pi(q_{\lambda})=(0,0.5,0.5)$. Tree arcs are labeled with quantization
vectors. To simplify the visualization, only partition indexes are shown. For
instance, $(0,5,5)$ corresponds to the quantization vector
$(I_{10}^{0},I_{10}^{5},I_{10}^{5})$. The root $\lambda$ of the tree has an
arc for each one of the classes in which quantization partitions the set of
probability distributions of the states of the PDFA. In the example, there are
three, namely quantization vectors $(0,5,5)$, $(1,6,3)$, and $(1,3,6)$,
corresponding to distributions $(0,0.5,0.5)$, $(0.1,0.6,0.3)$, and
$(0.1,0.3,0.6)$, respectively. The tree explains that states $q_{\lambda}$ and
$q_{1}$ are not equivalent, i.e., $\left[\lambda\right]=q_{\lambda}\not\equiv
q_{1}=\left[1\right]$, because
$\pi^{\ast}(\lambda|q_{\lambda})=\pi(q_{\lambda})\neq\pi(q_{1})=\pi^{\ast}(\lambda|q_{1})$,
and they are distinguished by $\lambda\in Dis$. They are also not equivalent
to $q_{0}$ and $q_{10}$ for the same reason. These two states, which have the
same probability distribution, are indeed distinguished by the string $1\in
Dis$ because
$\pi^{\ast}(1|q_{0})=\pi(q_{10})\neq\pi(q_{1})=\pi^{\ast}(1|q_{10})$.

#### Finding the class of a state (sifting)

Given a string $s^{\prime}\not\in Acc$, the tree allows to efficiently
determine its class $\left[s^{\prime}\right]$. That means either finding an
access string $s\in Acc$ such that $\left[s^{\prime}\right]=\left[s\right]$ or
creating a new class by adding $s^{\prime}$ to $Acc$. To this end, we define
the _sifting_ operation as follows. Sift starts at the root of $T$. Let $d\in
Dis$ be the distinguishing string at the current node of the tree. In this
case, we perform a membership query to get
$\left<\mathbf{MQ}_{\mathrm{QuaNT}}(s^{\prime}d)\right>$ and then we descend
to the subtree labeled with such quantization vector. Sift continues in this
manner until a leaf $s\in Acc$ is reached, in which case,
$\left[s\right]=\left[s^{\prime}\right]$. If there is no arc labeled with the
same quantization vector, we have discovered a new class and must update the
tree (_sift-update_) by adding $s^{\prime}$ to $Acc$ with probability
$\mathbf{MQ}_{\mathrm{QuaNT}}(s^{\prime})$ and a new arc
$(d,\left<\mathbf{MQ}_{\mathrm{QuaNT}}(s^{\prime}d)\right>,s^{\prime})$.
Sifting can be efficiently implemented because the number of membership
queries is bounded by the depth of $T$, and finding quantization vectors and
asking membership queries can be cached to minimize the number of vector
comparisons and queries to the target system, respectively.

#### Building a tentative hypothesis $\widehat{A}$

Given a tree $T$, it is easy to construct $\widehat{A}$ using sift. Each state
of $\widehat{A}$ is uniquely identified with an access string in $Acc$. For
each state $q_{s}$, $s\in Acc$, and symbol $\sigma\in\Sigma$,
$\tau(q_{s},\sigma)=q_{s^{\prime}}$, where
$s^{\prime}=\mathrm{sift}(s\sigma)$, and $\pi(q_{s})$ is the probability
distribution associated with the leaf node $s$. In the case that sift
generates an update, the building process is restarted. Because of Prop. 5,
this eventually terminates. Moreover, by construction, $\widehat{A}$ is a
PDFA.

#### Equivalence queries

For $\mathbf{EQ}_{\mathrm{QuaNT}}$ we use an adaptation of Hopcroft-Karp where
states are compared as follows:
$\left<\pi(\widehat{q})\right>_{\kappa}=\left<\pi(q)\right>_{\kappa}$, where
$q$ is a state of the target PDFA $A$ and $\widehat{q}$ is a state of the
hypothesis PDFA $\widehat{A}$.

#### Processing a counterexample

Let $\gamma$ be a counterexample returned by $\mathbf{EQ}_{\mathrm{QuaNT}}$,
that is $\pi^{\ast}_{A}(\gamma)\neq_{\kappa}\pi^{\ast}_{\widehat{A}}(\gamma)$.
Let $\gamma_{i}$ be the $i$-th symbol of $\gamma$, $\gamma[i]$ be the prefix
of $\gamma$ of length $i$, i.e., $\gamma[i]=\gamma_{1}...\gamma_{i}$,
$s_{i}=\mathrm{sift}(\gamma[i])$, and $\widehat{s}_{i}$ the string associated
to the state $\tau^{\ast}_{\widehat{A}}(\gamma[i])$. Let $1\leq j\leq|\gamma|$
be the first index such that $\widehat{s}_{j}\neq s_{j}$. This means that
$\left[\widehat{s}_{j}\right]\neq\left[s_{j}\right]$ and
$\widehat{s}_{j-1}=s_{j-1}$, but the states reached by $\widehat{A}$ and $A$
after traversing $\gamma[j-1]$ are not equivalent since when continued with
$\gamma_{j}$ they reach non-equivalent states. That is,
$\left[s_{j-1}\right]\neq\left[\gamma[j-1]\right]$. Therefore, $T$ has to be
updated by adding a new leaf node $\gamma[j-1]$ representing the newly
discovered class. Then, $\gamma[j-1]$ is added to $Acc$. Now, let $d\in Dis$
be the least common ancestor in $T$ of $\widehat{s}_{j}$ and $s_{j}$. Then
$\gamma_{j}d$ is a distinguishing string for $s_{j-1}$ and $\gamma[j-1]$. In
terms of tree operations, the leaf $s_{j-1}$ is replaced by an inner node
$\gamma_{j}d$ and two children, namely $s_{j-1}$ and $\gamma[j-1]$.

1

Parameter : Quantization Parameter $\kappa$

Output : PDFA $\widehat{A}$

2

3$\widehat{A}\leftarrow\mathrm{BuildSingleStatePDFA}(\kappa)$;

4 $\gamma\leftarrow\mathbf{EQ}_{\mathrm{QuaNT}}(\widehat{A},\kappa)$;

5

6if  _$\gamma=\bot$_ then

7 return $\widehat{A}$;

8

9$T\leftarrow\mathrm{InitializeTree}(\gamma,\kappa)$;

10

11while  _$\gamma\neq\bot$_ do

12 $\widehat{A}\leftarrow\mathrm{BuildAutomaton}(T)$;

13 $\gamma\leftarrow\mathbf{EQ}_{\mathrm{QuaNT}}(\widehat{A},\kappa)$;

14

15 if  _$\gamma\neq\bot$_ then

16 $T\leftarrow\mathrm{UpdateTree}(T,\gamma,\kappa)$;

17

18

19return $\widehat{A}$;

Algorithm 1 $\mathrm{QuaNT}$

#### Complete algorithm

Algorithm 1 shows $\mathrm{QuaNT}$ pseudocode. The algorithm begins by
executing BuildSingleStatePDFA which creates an initial hypothesis
$\widehat{A}$, with a single state $q_{\lambda}$ with a loop for each symbol
and executes $\mathbf{MQ}_{\mathrm{QuaNT}}(\lambda)$ to get the probability
distribution for the state. Then, it calls
$\mathbf{EQ}_{\mathrm{QuaNT}}(\widehat{A},\kappa)$, which either returns
$\bot$ and terminates or a counterexample $\gamma$ enabling the initialization
of the tree. The first tree $T$ has a root labeled with the distinguishing
string $\lambda$ and two children, one with the access string $\lambda$ and
the other with the counterexample $\gamma$. Once $T$ is initialized, the main
loop of the algorithm begins. It consists in using $T$ to build a PDFA
$\widehat{A}$, then using $\mathbf{EQ}_{\mathrm{QuaNT}}$ to compare it with
the target PDFA $A$. If a counterexample is returned, $T$ is updated,
resulting in new states being discovered. Otherwise it means all states in
$Q{/_{\scriptscriptstyle\equiv_{\kappa}}}$ have been found which implies
$\widehat{A}\equiv_{\kappa}A$.

######  Proposition 6.

For any PDFA $A$, $\mathrm{QuaNT}$ terminates and computes a PDFA
$\widehat{A}\in A{/_{\scriptscriptstyle\equiv_{\kappa}}}$.

##  4 Experiments

In this section we present the results of the experiments carried out to
compare $\mathrm{QuaNT}$ with a clustering-based algorithm that uses an
observation table and a tolerance-based non-equivalence similarity relation,
similar to $\mathrm{WL}^{\ast}$, that we call $\mathrm{L_{p}^{\ast}}$ (see
Appendix A). We compared the learning algorithms on randomly generated PDFA.
The generation technique works in two steps. First, it constructs random DFA
over $\Sigma$. Second, DFA are transformed into PDFA by assigning a
probability distribution over $\Sigma_{\$}$ to every state. The first step
uses the method described in [11] based on results from [4]. Let $n$ be the
desired number of reachable states of a DFA, called its _nominal_ size. The
method consists in randomly generating DFA of a total of $n\cdot
m\cdot\rho_{m}^{-1}$ possibly unreachable states, for $m=|\Sigma|$, where
$\rho_{m}=m-W_{0}\cdot m\cdot e^{-m}$ and $W_{0}$ is the Lambert-W function,
and then computing its accessible part by a depth-first traversal. It is
important to remark that this method does not guarantee the _actual_ size of
the accessible part to be exactly $n$, but to be normally distributed around
$n$. To obtain exactly $n$ accessible states, the method could be repeated
using a rejection algorithm. However, in practice, this proved to be very
inefficient, being almost impossible to generate DFA of accessible size bigger
than 100 in reasonable time. All experiments threw perfect scores for all
computed metrics (word error rate, normalized discounted cumulative gain, log
probability error [15]) for all algorithms on the same test set of strings.
Therefore, the analyses of the experimental results are mainly focused on
execution time and structure size. For ease of comparison, figures show trend
lines.

###  4.1 Experiment 1

In this experiment we compared $\mathrm{QuaNT}$ and $\mathrm{L_{p}^{\ast}}$.
For this, 10 random PDFA over a binary alphabet ($m=2$) of nominal sizes
$n=100,200,300$ were generated, and each algorithm was run 10 times for each
PDFA. For $\mathrm{QuaNT}$ $\kappa=1000$, and for $\mathrm{L_{p}^{\ast}}$,
$t=\kappa^{-1}$ (Prop 4). Fig. 4(a) shows learning time medians for every
actual size. Notably, $\mathrm{L_{p}^{\ast}}$ execution time grows much faster
than $\mathrm{QuaNT}$’s. Indeed, $\mathrm{QuaNT}$ achieves a speedup of
approximately $0.2n$, reaching around 60x for the biggest PDFA (see Fig.
6(a)). This experiment also showed that the size of $\mathrm{L_{p}^{\ast}}$’s
observation table grows bigger than $\mathrm{QuaNT}$’s tree which partly
explains the gains in execution time (Fig. 4(b)).

###  4.2 Experiment 2

In this experiment 10 random PDFA of nominal size $n=100$ were generated for
alphabet size $m=2,4,8,16,32$. We compared $\mathrm{QuaNT}$ and
$\mathrm{L_{p}^{\ast}}$ with $\kappa=1000$ and $t=\kappa^{-1}$. Each algorithm
was run 10 times for each PDFA. Fig. 5(a) shows the learning time medians for
every alphabet size. As it can be seen $\mathrm{L_{p}^{\ast}}$ seems to be
more sensitive to the growth in the alphabet size.

###  4.3 Experiment 3

In this experiment, we compare the algorithms for different values of
tolerance and quantization parameter: $\kappa=10,100,500,1000,2000,3000$, with
$t=\kappa^{-1}$. For every parameter configuration 10 random PDFA of nominal
size $n=300$ and alphabet size $m=2$ were generated, and each algorithm was
run 10 times for each PDFA. Fig. 5(b) shows the median learning times. As it
can be seen both algorithms appear to stabilize its execution time after some
parameters sizes ($\kappa=500$, $t=1/1000$).

###  4.4 Experiment 4

Here, $\mathrm{QuaNT}$ was evaluated on bigger nominal sizes
$n=1000,2000,5000$, fixing $\kappa=1000$ and $m=2$. For every parameter
configuration, 10 random PDFA were generated and each algorithm was run 10
times for each PDFA. Fig. 6(b) shows median learning times. Clearly,
$\mathrm{QuaNT}$ still manages to learn PDFA from systems that are intractable
for $\mathrm{L_{p}^{\ast}}$. Assuming a linear speedup of $0.2n$ from
Experiment 4.1, the learning time of a PDFA of size 5000 would be almost a
month for $\mathrm{L_{p}^{\ast}}$.

###  4.5 Experiment 5

In previous experiments it is noted that nearly all states in the randomly
generated PDFA have distinct next symbol distributions, that is, most states
are distinguished by $\lambda$, thus producing shallow tree structures (depth
1 or 2). In order to analyze cases where states share next symbol
distributions we parameterized the PDFA random generation by a number $d$ of
distributions to use. The algorithm first randomly generates a set of $d$
distributions and then labels each state by uniformly picking one in this set.

For this experiment, 10 random PDFA over a binary alphabet ($m=2$) of nominal
size $n=300$ were generated for different values of $d$ (ranging from 2 to
16). Each algorithm was run 10 times for each PDFA. For $\mathrm{QuaNT}$,
$\kappa=1000$, and for $\mathrm{L_{p}^{\ast}}$, $t=\kappa^{-1}$ (Prop 4). Fig.
7(a) shows learning time medians for every $d$ value. Notably,
$\mathrm{L_{p}^{\ast}}$ execution time still grows faster than
$\mathrm{QuaNT}$’s. The only case where $\mathrm{QuaNT}$ achieves worse
learning time than $\mathrm{L_{p}^{\ast}}$ is for $d=2$. Otherwise,
$\mathrm{QuaNT}$ significantly benefits from the increase in $d$. Regarding
structure sizes, $\mathrm{L_{p}^{\ast}}$’s observation table grows bigger than
previous experiments, being negatively affected by smaller values of $d$.
However $\mathrm{QuaNT}$ maintains similar sizes to those observed in
experiment 1 (Fig. 7(b)).

##  5 Conclusions

We defined a robust notion of similarity of states in PDFA based on a
congruence over states and a quantization of their probability distributions.
This induces a precisely defined inductive bias for PDFA learning as a set of
quantized weakly minimal PDFA. Based on this, we developed a new PDFA active
MAT-learning algorithm called $\mathrm{QuaNT}$ which uses an n-ary tree to
efficiently learn a PDFA in the hypothesis space. In order to empirically
assess the efficiency of $\mathrm{QuaNT}$, we presented an adaptation of
$\mathrm{WL}^{\ast}$, namely $\mathrm{L_{p}^{\ast}}$, which works with a non-
equivalence similarity relation over distributions and an observation table.
Algorithms were compared on a number of randomly generated PDFA. The
experiments confirmed notable execution time gains achieved by
$\mathrm{QuaNT}$.

#### Acknowledgments

Research reported in this article has been partially funded by the following
grants: ANII-Agencia Nacional de Investigación e Innovación
FMV_1_2019_1_155913, and the ANR-JST CREST project on Formal Analysis and
Design of AI-intensive Cyber-Physical Systems (CyPhAI) funded by the French
National Research Agency ANR and Japan Science and Technology Agency JST.

## References

  * [1] D. Angluin.  Learning regular sets from queries and counterexamples.  Inf. Comput., 75(2):87–106, November 1987.
  * [2] A. Beimel, F. Bergadano, N. Bshouty, E. Kushilevitz, and S. Varricchio.  Learning functions represented as multiplicity automata.  Journal of the ACM, 47(3):506–530, 2000.
  * [3] F. Bergadano and S. Varricchio.  Learning behaviors of automata from multiplicity and equivalence queries.  SIAM Journal on Computing, 25(6):1268–1280, 1996.
  * [4] A. Carayol and C. Nicaud.  Distribution of the number of accessible states in a random deterministic automaton.  Leibniz Int. Proc. in Informatics, 14:194–205, 2012.
  * [5] A. Clark and F. Thollard.  PAC-learnability of probabilistic deterministic finite state automata.  J. Machine Learning Research, 5:473–497, 2004.
  * [6] C. de la Higuera.  Grammatical Inference: Learning Automata and Grammars.  Cambridge University Press, 2010.
  * [7] L. Feng, T. Han, M. Kwiatkowska, and D. Parker.  Learning-based compositional verification for synchronous probabilistic systems.  In ATVA’11, pages 511–521. LNCS 6996, 2011.
  * [8] M. Isberner, F. Howar, and B. Steffen.  The TTT algorithm: A redundancy-free approach to active automata learning.  In RV’14, pages 307–322. LNCS 8734, 2014.
  * [9] A. Kaznatcheev and P. Panangaden.  Weighted automata are compact and actively learnable.  Inf. Process. Lett., 171:106–133, 2021.
  * [10] M.J. Kearns and U.V. Vazirani.  An Introduction to Computational Learning Theory.  MIT Press, Cambridge, MA, USA, 1994.
  * [11] C. Nicaud.  Random deterministic automata.  In MFCS’14, pages 5–23. LNCS 8634, 2014.
  * [12] M. Tappler, B. K. Aichernig, G. Bacci, M. Eichlseder, and K. G. Larsen.  L*-based learning of markov decision processes (extended version).  Form. Asp. Comput., 33(4–5):575–615, 2021.
  * [13] F. Thollard, P. Dupont, and C. de la Higuera.  Probabilistic DFA inference using Kullback-Leibler divergence and minimality.  In 7th Conf. Machine Learning, page 975–982, 2000.
  * [14] W.G. Tzeng.  Learning probabilistic automata and markov chains via queries.  Machine Learning, 8:151–166, 1992.
  * [15] G. Weiss, Y. Goldberg, and E. Yahav.  Learning deterministic weighted automata with queries and counterexamples.  In Adv. in Neural Information Proc. Sys., volume 32, 2019.

##  Appendix A $\mathrm{L_{p}^{\ast}}$

Here we present $\mathrm{L_{p}^{\ast}}$, a variant of $\mathrm{WL}^{\ast}$
[15]. Similarly, it uses an observation table $O_{Pre,Suf}$ for storing
outcomes of $\mathbf{MQ}_{\mathrm{L_{p}^{\ast}}}$, where
$Pre\subset\Sigma^{\ast}$ is the set of _prefixes_ (stored in row indices) and
$Suf\subset\\{\$\\}\cup\Sigma^{+}$ is the set of _suffixes_ (stored in column
indices). For every $p\in Pre$ and $s\in Suf$,
$O_{Pre,Suf}[p,s]=\mathbf{MQ}_{\mathrm{L_{p}^{\ast}}}(ps)=\pi^{\ell}_{q_{\mathrm{in}}}(ps)$,
where $\pi^{\ell}$ is defined in (1). Unlike $\mathrm{WL}^{\ast}$, $Pre$ is
divided in two parts [6], namely _RED_ which are the rows used to construct
_states_ , and _BLUE_ which are the rows representing continuations. The
algorithm ensures that for every row in _RED_ all its continuations are in
$Pre$. $\mathrm{L_{p}^{\ast}}$ consists of three main steps. The first one
expands $O_{Pre,Suf}$ through the use of $\mathbf{MQ}_{\mathrm{L_{p}^{\ast}}}$
until it becomes _closed_ and _consistent_. The second one constructs a
hypothesis automaton using a greedy clustering technique rather than DBScan.
The third one calls $\mathbf{EQ}_{\mathrm{L_{p}^{\ast}}}$ with the proposed
hypothesis. For this we adapted Hopcroft-Karp algorithm for checking
$t$-similarity. When $A$ and $\widehat{A}$ are found to be not $t$-similar,
$\mathbf{EQ}_{\mathrm{L_{p}^{\ast}}}$ returns a counterexample which is added
to _RED_ together with all its prefixes, and all their continuations to _BLUE_
(provided they are not already in _RED_). These steps are repeated as long as
$\mathbf{EQ}_{\mathrm{L_{p}^{\ast}}}$ yields a counterexample, otherwise it
stops and returns the last hypothesis.

##  Appendix B Proofs

#### Proof of Proposition 1

  1. 1.

By hypothesis, $\pi^{\ast}(\lambda|q_{1})=\pi^{\ast}(\lambda|q_{2})$. By
definition, $\pi^{\ast}(\lambda|q_{i})=\pi(q_{i})$, $i=1,2$. Therefore,
$\pi(q_{1})=\pi(q_{2})$.

  2. 2.

By hypothesis, $\forall s\in\Sigma^{\ast}$, $\pi^{\ast}(\sigma
s|q_{1})=\pi^{\ast}(\sigma s|q_{2})$. By definition, $\pi^{\ast}(\sigma
s|q_{i})=\pi^{\ast}(s|\tau(q_{i},\sigma))$, $i=1,2$. Thus, $\forall
s\in\Sigma^{\ast}$,
$\pi^{\ast}(s|\tau(q_{1},\sigma))=\pi^{\ast}(s|\tau(q_{2},\sigma))$. Hence,
$\tau(q_{1},\sigma)\equiv\tau(q_{2},\sigma)$. ∎

#### Proof of Proposition 2

Clearly, for all $q,q^{\prime}\in Q$, if $q\equiv q^{\prime}$ then
$P(s|q)=P(s|q^{\prime})$ for every $s\in\Sigma^{\ast}$. Hence,
$P(s|\left[q_{\mathrm{in}}\right])=P(s|q_{\mathrm{in}})$. ∎

#### Proof of Proposition 3

Suppose that $A$ is not weakly minimal. Then, there are states in $A$ which
are equivalent. Thus, $A{/_{\scriptscriptstyle\equiv}}$, which computes the
same function as $A$, has strictly less states than $A$, which contradicts the
hypothesis. ∎

#### Proof of Proposition 4

$q\equiv_{\kappa}q^{\prime}$ implies
$\pi^{\ast}(s|q)=_{\kappa}\pi^{\ast}(s|q^{\prime})$ for all
$s\in\Sigma^{\ast}$. Therefore,
$\pi^{\ell}_{q}(s\sigma)=_{\kappa}\pi^{\ell}_{q^{\prime}}(s\sigma)$ for all
$s\in\Sigma^{\ast},\sigma\in\Sigma_{\$}$. Then,
$|\pi^{\ell}_{q}(s\sigma)-\pi^{\ell}_{q^{\prime}}(s\sigma)|\leq\kappa^{-1}$
for all $s\in\Sigma^{\ast},\sigma\in\Sigma_{\$}$. Hence,
$q\approx_{\kappa^{-1}}q^{\prime}$. ∎

#### Proof of Proposition 5

If $s,s^{\prime}\in Acc$ then $\left[s\right]\neq\left[s^{\prime}\right]$,
hence $|Acc|\leq|Q{/_{\scriptscriptstyle\equiv_{\kappa}}}|$. ∎

#### Proof of Proposition 6

Termination First notice that all inner operations terminate. Second, when a
counterexample is returned, the number of leaves of $T$ increases by at least
1. Therefore by Proposition 5 and the fact that
$|Q{/_{\scriptscriptstyle\equiv_{\kappa}}}|\leq|Q|$, $\mathrm{QuaNT}$
terminates.
Correctness When $\mathrm{QuaNT}$ terminates, the hypothesis $\widehat{A}$
constructed is such that
$\widehat{Q}=Q{/_{\scriptscriptstyle\equiv_{\kappa}}}$,
$\widehat{\pi}=\pi{/_{\scriptscriptstyle\equiv_{\kappa}}}$,
$\widehat{\tau}=\tau{/_{\scriptscriptstyle\equiv_{\kappa}}}$. Therefore
$\widehat{A}\equiv_{\kappa}A$. ∎

##  Appendix C Figures

$q_{0}$0$q_{1}$0.5$a/1$$a/0.5$

$\pi$ | $\tau$
---|---
$Q$ | $\$$ | $a$ | $a$
$q_{0}$ | 0 | 1 | $q_{1}$
$q_{1}$ | 0.5 | 0.5 | $q_{1}$

$q^{\prime}_{0}$0$q^{\prime}_{1}$$0.5+\varepsilon$$a/1$$a/0.5-\varepsilon$

Figure 1: ($a$-$b$) PDFA over $\Sigma=\\{a\\}$ with $q_{\mathrm{in}}=q_{0}$.
($c$) PDFA $A_{\varepsilon}$.

$q_{0}$0$q_{1}$0$q_{2}$0.3$q_{3}$0$a/0.1$$b/0.9$$b/0.2$$a/0.8$$a/0.1$$b/0.6$$a,b/0.5$

$q^{\prime}_{0}$0$q^{\prime}_{1}$0$q^{\prime}_{2}$0.3$q^{\prime}_{3}$0$q^{\prime}_{4}$0$a/0.1$$b/0.9$$b/0.2$$a/0.8$$a/0.2$$b/0.5$$a,b/0.5$$b/0.1$$a/0.9$

Figure 2: PDFA $A$ (left) and $B$ (right).

$\lambda$$\lambda$$(0,0.5,0.5)$$(0,5,5)$$1$$10$$(0.1,0.3,0.6)$$(1,6,3)$$0$$(0.1,0.3,0.6)$$(1,3,6)$$(1,3,6)$$1$$(0.1,0.6,0.3)$$(1,6,3)$

$q_{\lambda}$$0$$q_{1}$$0.1$$q_{0}$$0.1$$q_{10}$$0.1$$1/0.5$$0/0.5$$1/0.3$$0/0.6$$0/0.3$$1/0.6$$1/0.6$$0/0.3$

Figure 3: An n-ary classification tree (left), and the corresponding PDFA
(right)

(a) Execution time.

(b) Structure size.

Figure 4: Experiment 1

(a) Experiment 2.

(b) Experiment 3.

Figure 5: Experiments 2 and 3.

(a) Experiment 1 (Speedup).

(b) Experiment 4.

Figure 6: Experiments 1 (Speedup) and 4.

(a) Execution time.

(b) Structure size.

Figure 7: Experiment 5.


# Behavioural Movement Strategies in Cyclic Models

B. Moura  Institute for Biodiversity and Ecosystem Dynamics, University of
Amsterdam, Science Park 904, 1098 XH Amsterdam, The Netherlands
<EMAIL_ADDRESS>J. Menezes  Institute for Biodiversity and Ecosystem
Dynamics, University of Amsterdam, Science Park 904, 1098 XH Amsterdam, The
Netherlands<EMAIL_ADDRESS>
###### Abstract

The spatial segregation of species is fundamental to ecosystem formation and
stability. Behavioural strategies may determine where species are located and
how their interactions change the local environment arrangement. In response
to stimuli in the environment, individuals may move in a specific direction
instead of walking randomly. This behaviour can be innate or learned from
experience, and allow the individuals to conquer or the maintain territory,
foraging or taking refuge. We study a generalisation of the spatial rock-
paper-scissors model where individuals of one out of the species may perform
directional movement tactics. Running a series of stochastic simulations, we
investigate the effects of the behavioural tactics on the spatial pattern
formation and the maintenance of the species diversity. We also explore a more
realistic scenario, where not all individuals are conditioned to perform the
behavioural strategy or have different levels of neighbourhood perception. Our
outcomes show that self-preservation behaviour is more profitable in terms of
territorial dominance, with the best result being achieved when all
individuals are conditioned and have a long-range vicinity perception. On the
other hand, invading is more advantageous if part of individuals is
conditioned and if they have short-range neighbourhood perception. Finally,
our findings reveal that the self-defence strategy is the least jeopardising
to biodiversity which can help biologists to understand population dynamics in
a setting where individuals may move strategically.

## Introduction

The understanding of the spatial segregation of species is crucial for
ecology[1]. It is well known that ecosystem formation and stability depend on
the interaction among individuals [2, 3]. In this sense, it has been
enlightening the outcomes from experiments with bacteria Escherichia coli that
revealed that space plays a vital role in preserving biodiversity [4, 5]. It
was observed that only cyclic dominance is not enough to maintain
biodiversity, but individuals must interact locally, forming spatially
detached domains[6]. The cyclic dominance among the bacteria strains is
described by the rock-paper-scissors rules, where scissors cut paper, paper
wraps rock, rock crushes scissors [5, 7, 8]. This type of spatial interaction
between species has also been observed in groups of lizards [9] and coral
reefs[10]. For this reason, stochastic simulations of the rock-paper-scissors
game have been widely used to investigate biological systems[11, 12]. In these
models, random mobility competes with local interactions such as reproduction
and selection, promoting (low mobility) or jeopardising (high mobility)
biodiversity [13]. Recently, some authors have dedicated attention to study
population dynamics in spatial systems where individuals move according to
behavioural strategies. For example, individuals’ dispersal rate may vary
according to the resources available in their habitat. In this case, it has
been shown that species coexistence is strongly affected by the adaptive
movement[14]. Another approach considered that species react to the presence
of others, developing directional movement[15]. Using a telegrapher-taxis
formalism, the authors analysed the differential equations and concluded that
directional movement has a significant effect on the spatial distribution of
the species.

In this paper, we study cyclic nonhierarchical systems where individuals of
one out of species move motivated by a stimulus in the environment [16, 17,
18]. The movement strategy depends on the individuals’ behaviour and aims to
increase the species territorial dominance [19, 20]. Here, we assume two types
of behaviours to describe systems where individuals respond to a stimulus
either instinctively (innate behaviour) or based on the experience
(conditioned behaviour) [21]. First, as a foraging behaviour - in which
natural resources are exploited - we define two movement strategies: i) Attack
tactic: a directional movement that allows the individuals to go straight to
areas mostly occupied by the individuals they dominate [22, 23, 24, 25]; ii)
Anticipation tactic: a directional movement prompt by stalking target
individuals, going to patches where their incoming is likely [26, 27, 28, 29,
30, 31]. Second, as a defence behaviour - a reaction to a stimulus to prevent
any damage - we define the Safeguard tactic: individuals move towards
territories mostly occupied by individuals that give them protection [32, 33].
We aim to understand how the behavioural movement strategies change the
spatial patterns and, consequently, the highest density zones of each species.
Also, we address the effects of the tactics on the species coexistence[13].

To execute a behavioural movement strategy, an individual senses its
neighbourhood, identifying the direction with more target individuals[34, 35,
36]. As this ability varies among species, we define a perception radius to
describe how far the individual can perceive the vicinity[37, 38]. It has been
suggested that some individuals do not perform behavioural strategies. This
happens because they have not yet learned or, somehow, they cannot put the
tactic into practice [39, 34, 40]. Therefore, to make the model more
realistic, we describe the individual’s ability to execute the tactic by
defining a conditioning factor. Our goal is to discover what perception radius
and conditioning factor ensures the highest spatial density for the species
whose individuals perform the movement tactics.

Figure 1: Selection rules and directional movement tactics. (a) Illustration
of the selection rules among the species, which represents a generalisation of
the rock-paper-scissors game. (b) Illustration of the directional movement
tactics for individuals of species $1$. The solid ruby line represents the
Attack tactic, where individuals move towards the direction with more
individuals of species $2$. The dashed ruby line shows the Anticipation
tactic, that is a movement towards the path with more individuals of species
$3$. The dashed-dotted ruby line illustrates how individuals move when they
perform the Safeguard tactic, going towards the direction with more
individuals of species $4$. The concentric circumference arcs in the right
panel illustrate that individuals of species $2$, $3$, $4$, and $5$ always
move randomly. Figure 2: Snapshots of simulations of the generalisation of the
rock-paper-scissors game illustrated in Fig. 1 running in square lattices with
$500^{2}$ grid points. Each dot shows either an individual (according to the
colour scheme in Fig. 1) or an empty site (white dot). All simulations started
from the same random initial conditions. The snapshots show the spatial
patterns for the standard model (a), Attack (b), Anticipation (c), and
Safeguard tactics(d), respectively, at $t\,=\,5000$ generations. See also the
videos for the whole simulation for the Standard case
(https://youtu.be/Ndvk6Rg57m4), Attack (https://youtu.be/JGhkDAHSo74),
Anticipation (https://youtu.be/ZZp9QlOfv2Q), and Safeguard
(https://youtu.be/eFxWdLhIOuQ). The results were obtained for $R=3$ and
$s\,=\,r\,=\,m\,=\,1/3$.

## Results

We first investigated how directional movement tactics affect spatial patterns
(see Methods). Figure 2 shows the spatial patterns obtained from a $500^{2}$
simulation running for a timespan of $5000$ generations. Figure 2(a), 2(b),
2(c), and 2(d) show the spatial patterns captured at $t=5000$ for the standard
model, Attack, Anticipation, and Safeguard directional movement tactics,
respectively. See also the videos for the entire simulation for the standard
case (https://youtu.be/Ndvk6Rg57m4), Attack (https://youtu.be/JGhkDAHSo74),
Anticipation (https://youtu.be/ZZp9QlOfv2Q), and Safeguard
(https://youtu.be/eFxWdLhIOuQ). The colours follow the scheme in Fig. 1, where
ruby, blue, pink, green, and yellow dots represent individuals of species $1$,
$2$, $3$, $4$, and $5$, respectively. White dots indicate empty spaces. Figure
3(a) depicts the results for the dynamics of the species densities for the
standard model whereas Figs. 3(b), 3(c), and 3(d) show how $\rho_{i}$ changes
when individuals of species $1$ use Attack, Anticipation, and Safeguard
tactics respectively. Additionally, in Fig. 4, the effects of the behaviour on
the selection risks of each species were computed by $\zeta_{i}$, that shows
the probability of one individual of species $i$ disappearing within a unit
time interval. Figure 4(a) depicts the case where species $1$ move randomly,
while Figs. 4(b), 4(c), and 4(d) show the selection risks if individuals of
species $1$ move according to the Attack, Anticipation, and Safeguard tactics
respectively. In Figs. 3 and 4, the colours identify the species according to
Fig. 1, whereas in Fig. 3 the grey line shows the density of empty spaces.

Figure 3: Temporal changes of spatial densities $\rho_{i}$, with
$i=0,1,2,3,4,5$, where $i=0$ indicates the empty spaces and $i=1,2,3,4,5$
represent the species according to the illustration in Fig. 1. The results
were obtained from the simulations presented in Fig. 2. (a) Standard case,
https://youtu.be/Ndvk6Rg57m4. (b) Attack tactic, https://youtu.be/JGhkDAHSo74.
(c) Anticipation tactic, https://youtu.be/ZZp9QlOfv2Q. (d) Safeguard tactic,
https://youtu.be/eFxWdLhIOuQ.

Initially, individuals of all species are distributed aleatorily on the grid.
Because of the random initial condition, selection interactions are frequent
in the initial stage of the simulation. The result is the formation of spirals
whose adjacent arms are mostly occupied by individuals of species that do not
select each other. In the standard model, the spirals are symmetric (Fig.
2(a)), leading to a cyclic territorial dominance of the species (Fig. 3(a))
and selection risks (Fig. 4(a)). This symmetry is broken if individuals of
species $1$ perform a directional movement tactic. Firstly, if the individuals
of species $1$ use the Attack tactic, they have more chances of selecting
because they move towards the direction with more individuals of species $2$
\- even though the selection probability $s$ is the same for all species. The
higher selection rate for species $1$ is responsible for the alternating
territorial dominance verified in the early stage of the pattern formation
shown in the video https://youtu.be/JGhkDAHSo74 (see Ref. [41]). The reason is
that when the number of individuals of species $2$ decreases, the population
of species $3$ rises, reducing the population of species $4$ and allowing the
population growth of species $5$. The consequence is that more individuals of
species $5$ lead to a higher selection risk of species $1$, as it is showed in
Fig. 4(b). Therefore, although the higher selection rate for species $1$, it
does not dominate when individuals perform the Attack tactic. Instead, species
$3$ is more abundant, as it is depicted in Fig. 3(b). Secondly, if the
individuals of species $1$ use the Anticipation tactic (they go towards the
direction with more individuals of species $3$), species $2$ is preserved, and
its population grows. There is a consequent reduction of the number of
individuals of species $3$, allowing the population of species $4$ to grow,
which limits the number of individuals of species $5$. Even though this
scenario appears to be favourable to species $1$, the fewer individuals of
species $5$ do not imply a less selection risk for species $1$, as it is shown
in Fig. 4(c). The selection risk of species $1$ is high because its population
growth is restricted since individuals of species $1$ go apart from
individuals of species $2$, making it difficult to conquer territory. Thirdly,
if the Safeguard tactic is used, the population growth of species $1$ is
expected due to the protection provided by individuals of species $4$ against
eventual attacks of individuals of species $5$. Mostly, when the individuals
of species $5$ approach individuals of species $1$, they find guards, which
destroy them. This effect is reinforced with the population growth of species
$2$, which controls the population size of species $3$, leading to a higher
abundance of individuals of species $4$ \- the more individuals of species
$4$, the more available refuges for species $1$. The result is a relevant
decreasing in the selection risk of the species $1$, as it is depicted in Fig.
4(d). As a consequence, the density of species $1$ is the highest, according
to Fig. 3, that shows that species $1$ dominate during the entire simulation,
with species $4$ being the second most abundant one.

Figure 4: Dynamics of the species selection risks $\zeta_{i}$ for the
simulations presented in Fig. 2. The colours indicate the species following
the scheme in Fig. 1. (a) Standard case, https://youtu.be/Ndvk6Rg57m4. (b)
Attack tactic, https://youtu.be/JGhkDAHSo74. (c) Anticipation tactic,
https://youtu.be/ZZp9QlOfv2Q. (d) Safeguard tactic,
https://youtu.be/eFxWdLhIOuQ.

### Autocorrelation Function

Figure 5: Autocorrelation functions $C_{i}$. The colours follow the scheme in
Fig. 1. (a), (b) , and (c) depict the cases where individuals of species $1$
use Attack, Anticipation, and Safeguard tactics, respectively. Grey circles
show the results for the autocorrelation function for the standard model
(std), that is the same for every species. The error bars indicate the
standard deviation. The horizontal black line indicates the threshold assumed
to calculate the characteristic length. The results were obtained using $R=3$
and $s\,=\,r\,=\,m\,=\,1/3$.

To quantify the effects of the directional movement tactics on the spatial
patterns, we calculated the spatial autocorrelation function $C_{i}(r)$, with
$i=1,...,5$ (See Methods). Figures 5(a), 5(b), and 5(c) show the spatial
autocorrelation function for the cases where individuals of species $1$ use
the Attack, Anticipation, and Safeguard tactics, respectively. The error bars
indicate the standard deviation from a set of $100$ simulations running in
square lattices of $500^{2}$ grid points. We computed the characteristic
length $l_{i}$, defined as $C(l)=0.15$ in every case, as illustrated by the
horizontal black line. In the standard model, the characteristic length is the
same for all species: $l_{i}=14$, with $i=1,..,5$. However, if individuals of
species $1$ moves according to the Attack tactic, the characteristic length of
species $1$, $3$ , and $4$ enlarges ($l_{1}=l_{3}=17$, and $l_{4}=15$) while
the characteristic length of species $2$ and $5$ decreases ($l_{2}=12$ and
$l_{5}=0.13$). For the Anticipation tactic, the characteristic length enlarges
for all species ($l_{1}=18$, $l_{2}=l_{3}=22$, $l_{4}=20$, and $l_{5}=18$).
Finally, for the Safeguard tactic, with exception of the species $3$ whose
characteristic length decreases ($l_{3}=12$), all other species have an
elongation in the characteristic length ($l_{1}=16$, $l_{2}=15$,
$l_{4}=l_{5}=17$).

### The Influence of the Perception Radius

To understand the role of the perception radius on the behavioural strategies,
we run a series of simulations for $1\,\leq\,R\,\leq\,5$. Figures 6(a), 6(b),
and 6(c) depict the mean spatial densities $\langle\rho_{i}\rangle$, with
$i=0,...,5$, for the Attack, Anticipation, and Safeguard tactics used by
individuals of species $1$, respectively ($\langle\rho_{0}\rangle$ indicates
the density of empty spaces). Figures 6(d), 6(e), and 6(f) depict the
selection risks $\langle\zeta_{i}\rangle$, with $i=1,...,5$, for the Attack,
Anticipation, and Safeguard tactics, respectively. Each circle shows the mean
value, while the error bars represent the standard deviation. We also
calculated the variation coefficient for our statistical results.

Figure 6: Mean species densities $\langle\rho_{i}\rangle$ and mean selection
risks $\langle\zeta_{i}\rangle$ as a function of the perception radius $R$.
$R=0$ represents the standard case. (a), (b), and (c) show
$\langle\rho_{i}\rangle$ for Attack, Anticipation, and Safeguard tactics,
respectively. (d), (e), and (f) depict $\langle\zeta_{i}\rangle$ for Attack,
Anticipation, and Safeguard tactics, respectively. The colours are the same as
in Fig. 3 and 4. The error bars indicate the standard deviation. The results
were obtained using $R=3$ and $s\,=\,r\,=\,m\,=\,1/3$.

For the standard model, $\langle\rho_{0}\rangle\approx 0.03$,
$\langle\rho_{i}\rangle\approx 0.194$, and $\langle\zeta_{i}\rangle\approx
0.028$ for $i=1...,5$. In the Attack tactic, the directional mobility is
advantageous for species $1$ for $R<3$. Figure 6(a) shows that
$\langle\rho_{2}\rangle\,<\,0.194$ for any $R$. In comparison with the
standard case, this indicates a harmful effect on the population of species
$2$, benefitting species $3$. Indeed, the selection risk of species $2$ is
always higher than in the standard model, as it is depicted in Fig. 6(d). As
the perception radius grows, the damage on the population of species $2$
becomes more significant. But, a higher $\langle\zeta_{2}\rangle$ does not
imply a growth of the population of species $1$. For the Anticipation tactic,
for a large $R$, the chances of the direction with more individuals of species
$3$ attracting individuals of species $1$ are greater, i.e., it is more likely
that individuals of species $1$ discard the path with more individuals of
species $2$. This is propitious to species $2$ conquer territory. For $R>2$,
this territorial dominance is such significant that allows that individuals of
species $1$ find individuals of species $2$ due to the Anticipation movement
tactic. However, although the Anticipation tactic represents a profit in terms
of spatial density for species $1$ for $R>2$, it is not advantageous compared
to the standard mobility: $\langle\rho_{1}\rangle\,<\,0.194$ for any
perception radius. Furthermore, the Anticipation movement tactic by
individuals of species $1$ provokes a reduction of selection risks for all
species. This effect is reflected in a lower density of empty spaces, and
becomes more relevant when $R$ enlarges. Finally, according to Fig. 6(c), the
Safeguard tactic is profitable for species $1$ when compared with the standard
model, irrespective of $R$. Moreover, the larger the perception radius, the
more efficient the behavioural strategy is - reducing the selection risk of
species $1$ becomes significant. However, for $R>3$, the high density of the
species $1$ results in small unavoidable population growth of species $5$,
which controls the population growth of species $1$.

### The Role of the Conditioning Factor

We studied how the proportion of conditioned individuals of species $1$
influences the results. We calculated the average density of species $1$,
$\langle\rho_{1}\rangle$ for the entire range of conditioning factor,
$0\,\leq\,\alpha\,\leq 1$. Figure 7 depicts the variation of
$\langle\rho_{1}\rangle$ in terms of $\alpha$, with $\alpha\,=\,0$
representing the standard case. The results show that Anticipation tactic is
disadvantageous for species $1$: the spatial densities
$\langle\rho_{1}\rangle$ is lower than the standard case, irrespective of
$\alpha$. In contrast, Safeguard tactic is always advantageous - the more
frequently the Safeguard tactic is used, the greater the fraction of the grid
occupied by individuals of the species $1$ is. Concerning to the Attack
tactic, the results show that for $0\,<\,\alpha\,\leq\,1$, there is a growth
of $\langle\rho_{1}\rangle$, that is maximum for $\alpha\,=\,0.4$.

Figure 7: Mean density of species $1$ in terms of the conditioning factor
$\alpha$. The green, red, and blue dashed lines show the results for the cases
of individuals of species $1$ moving according to Attack, Anticipation, and
Safeguard tactics, respectively. The error bars show the standard deviation.
The results were obtained using $R=3$ and $s\,=\,r\,=\,m\,=\,1/3$.

### Coexistence Probability

To observe the effects of the directional movement tactics on biodiversity, we
calculated the coexistence probability. To this purpose, we performed $2000$
simulations using $100^{2}$ lattices, running until $10000$ generations, for a
wide range of mobility probability $m$. The yellow line in Figure 8 shows the
coexistence probability for the standard model. The green, red, and blue lines
show the results when individuals of species $1$ use Attack, Anticipation and
Safeguard directional tactics, respectively. Solid lines and dashed lines show
the results for $R=2$ and $R=4$, respectively. Generally speaking, the chances
of individuals of all species remain at the end of the simulation decrease as
$m$ grows, independent of the specific behavioural tactic. Furthermore,
whether individuals of species $1$ move directionally, the coexistence is less
probable to maintain. The results indicate that for small $R$, Anticipation is
the tactic that threatens the most coexistence, while for large $R$ is Attack
tactic that most puts biodiversity in risk. In both cases, the Safeguard
tactic is the directional movement that less endangers the coexistence.

Figure 8: Coexistence probability as a function of the mobility probability
$m$. The solid yellow line shows the coexistence probability for the standard
model. The green, red, and blue lines show the results for the case of
individuals of species $1$ moving according to Attack, Anticipation, and
Safeguard directional tactics, respectively. Solid lines and dashed lines show
the results for $R=2$ and $R=4$, respectively. The results were obtained by
running $2000$ simulations in lattices with $100^{2}$ grid points running
until $100^{4}$ generations, with $s\,=\,r\,=\,(1-m)/2$.

## Discussion

We investigated a stochastic model of $5$ species, in which selection rules
are a generalisation of the nonhierarchical cyclic rock-paper-scissors game.
Based on the individual’s behaviour, we explored various directional movement
tactics for one out of the species. Although we implemented directional
mobility for only one species, all species are affected because of the cyclic
selection rules. The impact depends on the fraction of individuals that
perform the behavioural strategy and how far they can perceive the
neighbourhood.

To the best of our knowledge, this is the first time that simulations were
performed assuming that all individuals within the perception range equally
influence the directional movement tactic. Recently, some authors addressed a
model for directional movement in which the individual’s perception decreases
exponentially with the distance[42]. In that model, an individual chooses the
direction to move mostly influenced by the first immediate neighbours,
independent of its perception radius. Another difference in that model is that
directional mobility is implemented for all species. This makes the effects of
the individual’s behaviour compensated by the cyclic game. Here, we focused on
how a directional movement tactic used by one out of the species changes the
spatial patterns and, consequently, species spatial densities. We also
investigate the impact on the coexistence probability.

The main result of our investigation indicates that the individual’s behaviour
plays a central role in population dynamics of spatial biological systems. Our
statistical results are robust and reveal that the behaviour of self-
preservation is more profitable in terms of population growth. The simulations
showed that Safeguard is the directional movement tactic that brings more
profit in terms of spatial density when compared with the standard model.
More, the highest gain is achieved if: i) the perception radius of the
individuals is maximum; ii) the totality of individuals always perform the
Safeguard tactics. In opposite, the Attack tactic is more beneficial for the
species if individuals have a short perception radius and intercalate between
directional and random motion (for $R=3$, the higher spatial density is
achieved when only $40\%$ of individuals move directionally). Finally, the
results suggest that Anticipation tactic is disadvantageous, independent of
the perception radius and the fraction of the conditioned individuals. This
outcome may contribute for explaining the persistence of species whose part of
the individuals are not able to learn or perceive the neighbourhood (see [34,
40], for example).

The results can be extended to systems with a generic number of species $N$,
with odd $N$, where spirals with $N$ arms form the spatial patterns. The
adjacent arms are mostly occupied by individuals of species that do not select
each other. For example, for a system with $N=5$ species, the spiral arms are
occupied by individuals of species in the following order:
$\\{i+1;i-2;i;i+2;i-1\\}$. For an arbitrary $N$, there are $(N-3)/2$ arms
between the spatial concentrations of individuals of species $i$ and $i+1$,
with $i=1,..,N$. This means that for the Attack tactic to be efficient, the
perception radius $R$ must be larger as the number of species increases. In
contrast, regardless of the number of species, Anticipation and Safeguard
tactics efficiency is not ruined. The reason is that the spiral arms occupied
mostly by individuals of the species $i$ are always adjacent to the arms
populated by individuals of the species $i-2$ (outer arm) and to the arms
mainly formed by individuals of the species $i+2$ (inner arm). In the specific
case of Anticipation tactic, individuals of species $i$ discover where the
individuals $i+2$ concentrate, moving towards the opposite direction to the
spiral wave propagation. This reduces the selection risks of all species, and,
consequently, the density of empty spaces. On the other hand, if the Safeguard
tactic is applied, groups of individuals of the $i-2$ species are perceived,
making individuals of species $i$ to move towards the spiral wave propagation
direction.

In our model, a single species evolves into one movement tactic, while
individuals of the other species move randomly. In this scenario, when an
individual of the species $i$ anticipates, it aims to arrive earlier in the
areas where individuals of the species $i+1$ will multiply. However,
individuals of species $i+1$ do not walk directly towards the place the
individual of species $i$ is waiting for them, but it depends on the
simulation stochasticity. Suppose that except for the species $i$, all other
species use Attack tactic. Now, individuals of the species $i$ are guaranteed
that individuals of the species $i+1$ will go wherever they are, intensifying
the effects of the Anticipation tactics presented in this paper. Likewise, let
us consider that individuals of species $i$ use the Safeguard tactic, and
every species else performs the Attack tactic. In this scenario, as
individuals of species $i-1$ chase individuals of species $i$, the shelter
offered by individuals of the species $i-2$ becomes more relevant. We conclude
that Anticipation and Safeguard tactics may give more advantage in terms of
population growth for one species if individuals of the others perform the
Attack tactics. However, this effect may compromise biodiversity because if
individuals of one out of the species move directionally, the coexistence
probability decreases. Our findings may be useful to understand population
dynamics and biodiversity and describe complex systems in other areas of
nonlinear science.

## Methods

In this work, we performed stochastic simulations of a cyclic nonhierarchical
system composed of $5$ species. To this purpose, we implemented a standard
numerical algorithm largely used to study spatial biological systems [13, 41,
11]. We considered a generalisation of the rock-paper-scissors game for $5$
species, whose rules are illustrated in Fig. 1(a). The arrows indicate a
cyclic dominance among the species. Accordingly, individuals of species $i$
beat individuals of species $i+1$, with $i=1,2,3,4,5$.

The dynamics of individuals’ spatial organisation occurs in a square lattice
with periodic boundary conditions, following the rules: selection,
reproduction, and mobility. We assumed the May-Leonard implementation so that
the total number of individuals is not conserved [43]. Each grid point
contains at most one individual, which means that the maximum number of
individuals is $\mathcal{N}$, the total number of grid points.

Initially, the number of individuals is the same for all species, i.e.,
$I_{i}\,=\,\mathcal{N}/5$, with $i=1,2,3,4,5$ (there are no empty spaces in
the initial state). We prepared the initial conditions by distributing each
individual at a random grid point. At each timestep, one interaction occurs,
changing the spatial configuration of individuals. The possible interactions
are:

  * •

Selection: $i\ j\to i\ \otimes\,$, with $j=i+1$, where $\otimes$ means an
empty space; every time one selection interaction occurs, the grid point
occupied by the individual of species $i+1$ vanishes.

  * •

Reproduction: $i\ \otimes\to i\ i\,$; when one reproduction is realised an
individual of species $i$ fills the empty space.

  * •

Mobility: $i\ \odot\to\odot\ i\,$, where $\odot$ means either an individual of
any species or an empty site; an individual of species $i$ switches positions
with another individual of any species or with an empty space.

In our stochastic simulations, selection, reproduction, and mobilities
interactions occur with the following probabilities: $s$, $r$ and $m$,
respectively. We assumed that individuals of all species have the same
probabilities of selecting, reproducing and moving. The interactions were
implemented by assuming the von Neumann neighbourhood, i.e., individuals may
interact with one of their four nearest neighbours. The simulation algorithm
follows three steps: i) sorting an active individual; ii) raffling one
interaction to be executed; iii) drawing one of the four nearest neighbours to
suffer the sorted interaction (the only exception is the directional mobility,
where the neighbour is chosen according to the movement tactic). If the
interaction is executed, one timestep is counted. Otherwise, the three steps
are redone. Our time unit is called generation, defined as the necessary time
to $\mathcal{N}$ timesteps to occur.

In our model, individuals of one out of the species can move into the
direction with more individuals of a target species. The choice is based on
the strategy assumed by species. We assumed three sorts of directional
movement tactics:

  * •

Attack tactic: an individual of species $i$ moves into the direction with more
individuals of species $i+1$;

  * •

Anticipation tactic: an individual of species $i$ goes towards the direction
with a larger number of individuals of species $i+2$;

  * •

Safeguard tactic: an individual of species $i$ walk into the direction with a
larger concentration of individuals of species $i-2$.

In the standard model, individuals of all species move randomly.

We considered that only individuals of species $1$ perform the directional
movement tactics, as illustrated in Figure 1(b). The solid, dashed, and
dashed-dotted lines represent the Attack, Anticipation, and Safeguard tactics,
respectively. The concentric circumference arcs show that individuals of
species $2$, $3$, $4$, and $5$ always move randomly. For implementing a
directional movement, the algorithm follows the steps: i) it is assumed a disc
of radius $R$ (the perception radius), in the active individual’s
neighbourhood; ii) it is defined four circular sectors in the directions of
the four nearest neighbours; iii) according to the movement tactic, the target
species is defined: species $2$, $3$, and $4$, for Attack, Anticipation, and
Safeguard tactics, respectively; iv) it is counted the number of individuals
of the target species within each circular sector. Individuals on the borders
are assumed to be part of both circular sectors; v) the circular sector that
contains more individuals of the target species is chosen. In the event of a
tie, a draw between the tied directions is made; vi) the active individual
switches positions with the immediate neighbour in the chosen direction. The
swap is also executed in case of the neighbour grid point is empty.

To observe the spatial patterns, we first performed a single simulation for
the standard model, Attack, Anticipation, and Safeguard tactics. The
realisations run in square lattices with $500^{2}$ grid points, for a timespan
of $5000$ generations. We captured $500$ snapshots of the lattice (in
intervals of $10$ generations), that were used to make the videos of the
dynamics of the spatial patterns showed in https://youtu.be/Ndvk6Rg57m4
(standard), https://youtu.be/JGhkDAHSo74 (Attack),
https://youtu.be/ZZp9QlOfv2Q (Anticipation), and https://youtu.be/eFxWdLhIOuQ
(Safeguard). The final snapshots were depicted in Fig. 2(a), Fig. 2(b), Fig.
2(c), and Fig. 2(d). Individuals of species $1$, $2$, $3$, $4$, and $5$ are
identified with the colours ruby, blue, pink, green, and yellow, respectively;
while white dots represent empty spaces. The simulations were performed
assuming selection, reproduction, and mobility probabilities: $s=r=m=1/3$. The
perception radius was assumed to be $R=3$.

The population dynamics were studied by means of the spatial density
$\rho_{i}$, defined as the fraction of the grid occupied by individuals of
species $i$ at time $t$, i.e., $\rho_{i}=I_{i}/\mathcal{N}$, where $i=0$
stands for empty spaces and $i=1,...,5$ represent the species $1$, $2$, $3$,
$4$, and $5$. The temporal changes in spatial densities of the simulations
showed in Fig. 2 were depicted in Fig. 3, where the grey, ruby, blue, pink,
green, and yellow lines represent the densities of empty spaces and species
$1$, $2$, $3$, $4$, and $5$, respectively. We also computed how the selection
risk of individuals of species $i$ changes in time. To this purpose, the
algorithm counts the total number of individuals of species $i$ at the
beginning of each generation. It is then counted the number of times that
individuals of species $i$ are killed during the generation. The ratio between
the number of selected individuals and the initial amount is defined as the
selection risk of species $i$, $\zeta_{i}$. The results were averaged for
every $50$ generations. Figure 4 shows $\zeta_{i}\,(\%)$ as a function of the
time for the simulations presented in Fig. 2. The ruby, blue, pink, green, and
yellow lines show the selection risks of individuals of species $1$, $2$, $3$,
$4$, and $5$, respectively.

To quantify the spatial organisation of the species, we studied the spatial
autocorrelation function. This quantity measures how individuals of a same
species are spatially correlated, indicating spatial domain sizes. Following
the procedure carried out in literature [44, 45, 46, 41, 42], we first
calculated the Fourier transform of the spectral density as
$C(\vec{r}^{\prime})=\mathcal{F}^{-1}\\{S(\vec{k})\\}/C(0)$, where the
spectral density $S(\vec{k})$ is given by
$S(\vec{k})=\sum_{k_{x},k_{y}}\,\varphi(\vec{\kappa})$, with
$\varphi(\vec{\kappa})=\mathcal{F}\,\\{\phi(\vec{r})-\langle\phi\rangle\\}$.
The function $\phi(\vec{r})$ represents the species in the position $\vec{r}$
in the lattice (we assumed $0$, $1$, $2$, $3$, $4$, and $5$, for empty sites,
and individuals of species $1$, $2$, $3$, $4$, and $5$, respectively). We then
computed the spatial autocorrelation function as

$C(r^{\prime})=\sum_{|\vec{r}^{\prime}|=x+y}\frac{C(\vec{r}^{\prime})}{min(2N-(x+y+1),(x+y+1)}.$

Subsequently, we found the scale of the spatial domains of species $i$,
defined for $C(l_{i})=0.15$, where $l_{i}$ is the characteristic length for
species $i$.

We calculated the autocorrelation function by running $100$ simulations using
lattices with $500^{2}$ grid points, assuming $s=r=m=1/3$ and $R=3$. Each
simulation started from different random initial conditions. We then captured
each species spatial configuration after $5000$ generations to calculate the
autocorrelation functions. Finally, we averaged the autocorrelation function
in terms of the radial coordinate $r$ and calculated the characteristic length
for each species. We also calculated the standard deviation for the
autocorrelation functions and the characteristic lengths. Figure 4 shows the
comparison of the results for Attack, Anticipation, and Safeguard strategies
with the standard model. The ruby, blue, pink, green, and yellow circles
indicate the mean values for species $1$, $2$, $3$, $4$, and $5$,
respectively. In the case of standard model, the mean values are represented
by grey circles, which are the same for all species. The error bars show that
standard deviation. The horizontal black line represents $C(l_{i})\,=\,0.15$.

To further explore the numerical results, we studied how the perception radius
$R$ influences species spatial densities and selection risks. We calculated
the mean value of the spatial species densities, $\langle\,\rho_{i}\,\rangle$
and the mean value of selection risks, $\langle\,\zeta_{i}\,\rangle$ from a
set of $100$ simulations in lattices with $500^{2}$ grid points, starting from
different initial conditions for $R=1,2,3,4,5$. We used $s\,=r\,=\,m\,=1/3$
and a timespan of $t=5000$ generations. The mean values and standard deviation
were calculated using the second half of the simulations, thus eliminating the
density fluctuations inherent in the pattern formation process. The results
were shown in Fig. 6, where the circles represent the mean values and error
bars indicate the standard deviation. The colours are the same as in Fig. 3
and Fig. 4. Furthermore, to verify the precision of the statistical results,
we calculated the variation coefficient - the ratio between the standard
deviation and the mean value.

We studied a more realistic scenario where not all individuals of species $1$
can perform the directional movement tactics. For this reason, we defined the
conditioning factor $\alpha$, with $0\,\leq\,\alpha\,\leq\,1$, representing
the proportion of individuals of species $1$ that moves directionally. For
$\alpha=0$ all individuals move randomly while for $\alpha=1$ all individuals
move directionally. This means that every time an individual of species $1$ is
sorted to move, there is a probability $\alpha$ of the algorithm implementing
the directional movement tactic, instead of randomly choosing one of its four
immediate neighbours to switch positions. To understand the effects of the
conditioning factor, we observed how the density of species $1$ changes for
the entire range of $\alpha$, with intervals of $\Delta\alpha=0.1$. The
simulations were implemented for $R=3$ and $s\,=r\,=\,m\,=1/3$. It was
computed the mean value of the spatial density of species $1$,
$\langle\,\rho_{1}\,\rangle$, and its standard deviation from a set of $100$
different random initial conditions. The results were depicted in Fig. 7,
where the green, red, and blue dashed lines show $\langle\,\rho_{1}\,\rangle$
as a function of $\alpha$. The error bars indicate the standard deviation.

Finally, we aimed to investigate how the directional movement tactics
jeopardise species coexistence for a wide mobility probability range. Because
of this, we run $2000$ simulations in lattices with $100^{2}$ grid points for
$0.05\,<\,m\,<\,0.95$ in intervals of $\Delta\,m\,=\,0.05$, with $R=2$ and
$R=4$. The simulations started from different random initial conditions and
run for a timespan of $10000$ generations. Coexistence happens if at least one
individual of all species is present at the end of the simulation,
$I_{i}(t=5000)\neq 0$ with $i=1,2,3,4,5$. Otherwise, the simulation results in
extinction. The coexistence probability is the fraction of implementations
which results in coexistence. The simulations were performed for two values of
perception radius, $R=2$ and $R=4$; the selection and reproduction
probabilities were assumed to be $s\,=\,r\,=\,(1-m)/2$. The results were
depicted in Fig. 8, where yellow, green, red, and blue lines show the
coexistence probability as a function of $m$ for the standard model, Attack,
Anticipation, and Safeguard tactics, respectively. The solid and dashed lines
show the results for $R=2$ and $R=4$, respectively.

## References

  * [1] Begon, M., Townsend, C. R. & Harper, J. L.  _Ecology: from individuals to ecosystems_ (Blackwell Publishing, Oxford, 2006).
  * [2] Purvis, A. & Hector, A.  Getting the measure of biodiversity.  _Nature_ 405, 212–2019 (2000).
  * [3] Buchholz, R.  Behavioural biology: an effective and relevant conservation tool.  _Trends in Ecology & Evolution_ 22, 401 – 407 (2007).
  * [4] Kerr, B., Riley, M. A., Feldman, M. W. & Bohannan, B. J. M.  Local dispersal promotes biodiversity in a real-life game of rock–paper–scissors.  _Nature_ 418, 171 (2002).
  * [5] Kirkup, B. C. & Riley, M. A.  Antibiotic-mediated antagonism leads to a bacterial game of rock-paper-scissors in vivo.  _Nature_ 428, 412–414 (2004).
  * [6] Durret, R. & Levin, S.  Allelopathy in spatially distributed populations.  _J. Theor. Biol._ 185, 165–171 (1997).
  * [7] Albertson, R. C., Streelman, T., J. & Kocher, T. D.  Directional selection has shaped the oral jaws of lake malawi cichlid fishes.  _Proc. Nat. Acad. Sci._ 100, 5252–5257 (2003).
  * [8] Quinn, T. P., Hodgson, S., Flynn, L., Hilborn, R. & Rogers, D. E.  Directional selection by fisheries and the timing of sockeye salmon (oncorhynchus nerka) migrations.  _Ecol. Appl._ 17, 733–739 (2007).
  * [9] Sinervo, B. & Lively, C. M.  The rock-scissors-paper game and the evolution of alternative male strategies.  _Nature_ 380, 240–243 (1996).
  * [10] Volkov, I., Banavar, J. R., Hubbell, S. P. & Maritan, A.  Patterns of relative species abundance in rainforests and coral reefs.  _Nature_ 450, 45 (2007).
  * [11] Szolnoki, A., de Oliveira, B. F. & Bazeia, D.  Pattern formations driven by cyclic interactions: A brief review of recent developments.  _EPL (Europhysics Letters)_ 131, 68001 (2020).
  * [12] Szolnoki, A. _et al._ Cyclic dominance in evolutionary games: a review.  _Journal of The Royal Society Interface_ 11 (2014).
  * [13] Reichenbach, T., Mobilia, M. & Frey, E.  Mobility promotes and jeopardizes biodiversity in rock-paper-scissors games.  _Nature_ 448, 1046–1049 (2007).
  * [14] Park, J. & Jang, B.  Relativistic interplay between adaptative movement and mobility on biodiversity in the rock-paper-scissors game.  _J. KSIAM_ 24, 351–362 (2020).
  * [15] Potts, J. R.  Directionally correlated movement can drive qualitative changes in emergent population distribution patterns.  _Mathematics_ 7, 640 (2019).
  * [16] Fraenkel, G. S. & Gunn, D. L.  The orientation of animals. kineses, taxes, and compass reactions.  _The American Naturalist_ 75, 604 (1941).
  * [17] Bonte, D. & Dahirel, M.  Dispersal: a central and independent trait in life history.  _Oikos_ 126, 472–479 (2017).
  * [18] Cormont, A. _et al._ Effect of local weather on butterfly flight behaviour, movement, and colonization: significance for dispersal under climate change.  _Biodiversity and Conservation_ 20, 483–503 (2011).
  * [19] Bowler, D. E. & Benton, T. G.  Causes and consequences of animal dispersal strategies: relating individual behaviour to spatial dynamics.  _Biol Rev. Camb. Philos. Soc._ 80, 205–225 (2005).
  * [20] Torres, L. G., Orben, R. A., Tolkona, I. & Thompson, D. R.  Classification of animal movement behavior through residence in space and time.  _PLoS One_ 12, 1 (2016).
  * [21] Wilson, E. O.  _On Human Nature_ (Harvard University Press, Cambridge, MA, 2004).
  * [22] Torres, L. _et al._ White-capped albatrosses alter fine-scale foraging behavior patterns when associated with fishing vessels.  _Mar Ecol Prog Ser._ 428, 289–301 (2011).
  * [23] Kuefler, D., Avgar, T. & Fryxell, J. M.  Rotifer population spread in relation to food, density and predation risk in an experimental system.  _Journ. Anim. Ecol._ 81, 323 (2012).
  * [24] Kuefler, D., Avgar, T. & Fryxell, J. M.  Density- and resource-dependent movement characteristics in a rotifer.  _Functional Ecology_ 27, 323 (2013).
  * [25] Archer, J.  _The behavioural biology of agression_ (Cambridge University Press, Cambridge, 1988).
  * [26] Gerlee, P., Tunstrøm, K., Lundh, T. & Wennberg, B.  Impact of anticipation in dynamical systems.  _Phys. Rev. E_ 96, 062413 (2017).
  * [27] Nijhawan, R.  Motion extrapolation in catching.  _Nature_ 370, 256–257 (1994).
  * [28] Berry, M. J., Brivanlou, I. H., Jordan, T. A. & Meister, M.  Anticipation of moving stimuli by the retina.  _Nature_ 398, 334–338 (1999).
  * [29] Collett, T. S. & F., L. M.  How hoverflies compute interception courses.  _Journal of comparative physiology_ 125, 191 (1978).
  * [30] Borghuis, B. G. & Leonardo, A.  The role of motion extrapolation in amphibian prey capture.  _Journal of Neuroscience_ 35, 15430–15441 (2015).
  * [31] Rossel, S., Corlija, J. & Schuster, S.  Predicting three-dimensional target motion: how archer fish determine where to catch their dislodged prey.  _Journal of experimental biology_ 205, 3321 (2002).
  * [32] Altieri, A. H.  Dead zones enhance key fisheries species by providing predation refuge.  _Ecology_ 89, 2808–2818 (2008).
  * [33] Whitlow, W. L., Rice, N. A. & Sweeney, C.  Native species vulnerability to introduced predators: testing an inducible defense and a refuge from predation.  _Biological Invasions_ 5, 23–31 (2003).
  * [34] Sznajder, B., Sabelis, M. W. & Egas, M.  Innate responses of the predatory mite phytoseiulus persimilis to a herbivore-induced plant volatile.  _Exp. Appl. Acarol._ 54, 125–138 (2011).
  * [35] Pallini, A., Janssen, A. & Sabelis, M. W.  Odour-mediated responses of phytophagous mites to conspecific and heterospecific competitors.  _Oecologia_ 110, 179–185 (1997).
  * [36] Barraquand, F. & S., B.  Animal movements in heterogeneous landscapes: Identifying profitable places and homogeneous movement bouts.  _Ecology_ 89, 3336–3348 (2008).
  * [37] Maeda, T.  Correlation between olfactory responses, dispersal tendencies, and life-history traits of the predatory mite neoseiulus womersleyi (acari: Phytoseiidae) of eight local populations.  _Exp. Appl. Acarol._ 37, 67–82 (2005).
  * [38] Mariani, P., MarcKenzie, B. R., Visser, A. W. & Botte, V.  Individual-based simulations of larval fish feeding in turbulent environments.  _Mar. Ecol. Progr. Ser._ 347, 155–169 (2007).
  * [39] Revynthi, A. M., Egas, M., Janssen, A. & Sabelis, M. W.  Prey exploitation and dispersal strategies vary among natural populations of a predatory mite.  _Ecology and Evolution_ 8, 10384–10394 (2018).
  * [40] van Wijkm M., De Bruijn, P. J. A. & Sabelis, M. W.  Predatory mite attraction to herbivore-induced plant odors is not a consequence of attraction to individual herbivore-induced plant volatiles.  _J. Chem. Ecol._ 34, 791–803 (2008).
  * [41] Menezes, J., Moura, B. & Pereira, T. A.  Uneven rock-paper-scissors models: Patterns and coexistence.  _Europhysics Letters_ 126, 18003 (2019).
  * [42] Avelino, P. P. _et al._ How directional mobility affects coexistence in rock-paper-scissors models.  _Phys. Rev. E_ 97, 032415 (2018).
  * [43] May, R. M. & Leonard, W. J.  Nonlinear aspects of competition between three species.  _SIAM J. Appl. Math._ 29, 243–253 (1975).
  * [44] Smith, R. E. _et al._ Stable clustering, the halo model and non-linear cosmological power spectra.  _Mon. Not. R. Astron. Soc._ 341, 1311–1332 (2003).
  * [45] Hayashi, E. & White, S. D. M.  Understanding the halo-mass and galaxy-mass cross-correlation functions.  _Mon. Not. R. Astron. Soc._ 388, 2–14 (2008).
  * [46] Varghese, A. & Ilg, P.  Time correlation functions in the lebwohl-lasher model of liquid crystals.  _Phys. Rev. E_ 96, 0322705 (2017).

## Acknowledgements

We thank CNPq, FAPERN, ECT/UFRN, and IBED/University of Amsterdam for
financial and computational support.

## Author contributions statement

J. M. conceived the research project. B.M. performed the numerical
simulations. J. M. and B.M. analysed the results, wrote and revised the
manuscript.


and $(n-3)!$ orderings for the remaining elements. Hence, the expectation is
$1/((n-1)(n-2))$.

∎

We note that sampling from our solution generators is the reason that we
cannot find an optimal TSP solution efficiently. In general, an algorithm that
has converged to an almost optimal parameter $W^{\star}$ has to generate
samples from the Gibbs measure that is concentrated on cycles with minimum
weight. In this low-temperature regime, sampling is $\mathrm{NP}$-hard. We are
now ready to state our result.

######  Theorem 6 (TSP has a Compressed, Efficiently Optimizable Solution
Generator).

Consider a prior over TSP instances with $n$ nodes. For any $\epsilon>0$,
there exists a solution generator $\mathcal{P}=\\{p(w):w\in\mathcal{W}\\}$
such that $\mathcal{P}$ is complete, compressed with description
$\textnormal{poly}(n)\textnormal{polylog}(1/\epsilon)$ and
$\mathcal{L}+\lambda R:\mathcal{W}\mapsto\mathbb{R}$ is efficiently
optimizable via projected stochastic gradient descent in
$\textnormal{poly}(n,1/\epsilon)$ steps for some $\lambda>0$.

###### Proof.

Consider an input graph $G$ with $n$ nodes and weighted adjacency matrix $E$.
The feature vector is again a permutation matrix $\Pi$ with the additional
constraint that $\Pi$ has to represent a single cycle (a tour over all
cities). Then

$\texttt{TSP}=\min_{\Pi\in\mathbb{C}_{n}}E\cdot\Pi\,.$

The cost function for TSP is $L(\Pi;E)=\sum_{ij}E_{ij}M_{ij}\Pi_{ij}$. We
refer to Theorem 5 for the details about the feature mappings. We can finally
use Lemma 12 to obtain a variance lower bound (in the subspace induced by the
parameters satisfying this lemma, see Remark 9) under the uniform measure over
the space of cyclic permutation matrices $\mathbb{C}_{n}$. ∎

##  Appendix H Sampling and Counting

In this section, we give a quick overview of the connections between
approximate sampling and counting. For a formal treatment, we refer to
[Sin12].

In what follows, $\sigma$ may be thought of as an encoding of an instance of
some combinatorial problem, and the $\omega$ of interest are encodings of the
structures we wish to generate. Consider a weight function $W$ and assume that
$W(\sigma,\omega)$ is computable in time polynomial in $|\sigma|$.

######  Definition 4 (Approximate Sampling).

A fully polynomial approximate sampler for $(\Omega_{\sigma},\pi_{\sigma})$ is
a Probabilistic Turing Machine which, on inputs $\sigma$ and
$\epsilon\in\mathbb{Q}_{+}$ $(0<\epsilon\leq 1)$, outputs
$\omega\in\Sigma^{\star}$, according to a measure $\mu_{\sigma}$ satisfying
$\mathrm{TV}(\pi_{\sigma},\mu_{\sigma})\leq\epsilon$, in time bounded by a
bivariate polynomial in $|\sigma|$ and $\log(1/\epsilon)$.

One of the main applications of sampling is to approximate integration. In our
setting this means estimating $Z(\sigma)$ to some specified relative error.

######  Definition 5 (Approximate Integration).

A fully polynomial randomized approximation scheme for $Z(\sigma)$ is a
Probabilistic Turing Machine which on input $\sigma,\epsilon$, outputs an
estimate $\widehat{Z}$ so that

$\mathop{\bf Pr\/}[Z/(1+\epsilon)\leq\widehat{Z}\leq(1+\epsilon)Z]\geq 3/4\,,$

and which runs in time polynomial in $|\sigma|$ and $1/\epsilon$.

######  Definition 6 (Self-Reducible Problems).

An NP search problem is self-reducible if the set of solutions can be
partitioned into polynomially many sets each of which is in a one-to-one
correspondence with the set of solutions of a smaller instance of the problem,
and the polynomial size set of smaller instances are efficiently computable.

For instance, consider the relation MATCH which associates with an undirected
graph $G$ all matchings (independent sets of edges) of $G$. Then MATCH is
self-reducible since, for any edge $e=(u,v)\in E(G)$, we have that

$\texttt{MATCH}(G)=\texttt{MATCH}(G_{1})\cup\\{M\cup\\{e\\}:M\in\texttt{MATCH}(G_{2})\\}\,,$

where $G_{1}$ is the graph obtained by deleting $e$ and $G_{2}$ is the graph
obtained be deleting both $u$ and $v$ together with all their incident edges.

######  Theorem 7 (See Corollary 3.16 in [Sin12]).

For self-reducible problems, approximate integration and good sampling are
equivalent.

We remark that the above result holds for the more general class of self-
partitionable problems.

##  Appendix I Details of the Experimental Evaluation

We investigate the effect of the entropy regularizer (see Equation 2) in a
very simple setting: we try to find the Max-Cut of a fixed graph $G$, i.e.,
the support of the prior $\mathcal{R}$ is a single graph. We show that while
the unregularized objective is often “stuck” at sub-optimal solutions – and
this happens even for very small instances (15 nodes) – of the Max-Cut
problem, the regularized version (with the fast/slow mixture scheme) is able
to find the optimal solutions. We consider an instance randomly generated by
the Erdős–Rényi model $G(n,p)$ and then optimize the “vanilla” loss
$\mathcal{L}$ and the regularized loss $\mathcal{L}_{\lambda}$ defined in
Equation 3. The solutions are vectors $s\in\\{\pm 1\\}^{n}$. We first use the
feature mapping $\psi_{S}(s)=(ss^{\top})^{\flat}$ described in Section 1.1 and
an exponential family solution generator that samples a solution $s$ with
probability $\propto\exp(w\cdot\psi_{S}(s))$ for some weight vector
$w\in\mathbb{R}^{n^{2}}$. We also consider optimizing a simple 3-layer ReLU
network as solution generator with input $s\in\\{\pm 1\\}^{n}$ on the same
random graphs. We generate 100 random $G(n,p)$ graphs with $n=15$ nodes and
$p=0.5$ and train solution generators using both the ”vanilla” and the
entropy-regularized loss functions. We perform 600 iterations and, for the
entropy regularization, we progressively decrease the regularization weight,
starting from 10, and dividing it by $2$ every 60 iterations. We used a
fast/slow mixing with mixture probability 0.2 and inverse temperature rho=0.03
(see Figure 3). For convenience, we present a PyTorch implementation of our
simple 3-layer ReLU network here888For more details we refer to our full code,
that is available in the Supplementary Material of the NeurIPS 2023
Proceedings and the GitHub repository AlkisK/Solution-Samplers..

        class FastSlowMixture(torch.nn.Module):
        def __init__(self, dimension, rho):
            """
            The Model parameters.
            """
            super().__init__()

            self.l1 = torch.nn.Parameter(torch.empty(30, dimension))
            torch.nn.init.kaiming_uniform_(self.l1, a=5**0.5)

            self.l2 = torch.nn.Parameter(torch.empty(10, 30))
            torch.nn.init.kaiming_uniform_(self.l2, a=5**0.5)

            self.l3 = torch.nn.Parameter(torch.empty(1, 10))
            torch.nn.init.kaiming_uniform_(self.l3, a=5**0.5)

            self.a2 = torch.nn.ReLU()
            self.a1 = torch.nn.ReLU()

            self.rho = rho

        def forward(self, x, is_cold=True):

            temp = self.rho * (1. - is_cold) + is_cold

            out = x
            out = torch.nn.functional.linear(out, temp * self.l1)
            out = self.a1(out)
            out = torch.nn.functional.linear(out, temp * self.l2)
            out = self.a2(out)
            out = torch.nn.functional.linear(out, temp * self.l3)

            return out

Figure 3: Our implementation of the fast/slow network. The output of the
network is the log-density (score) of a solution $s\in\\{\pm
1\\}^{\mathrm{dimension}}$. If evaluated with the is-cold set to False, the
parameters of every linear layer are re-scaled by the inverse temperature rho.

Out of the 100 trials we found that our proposed objective was always able to
find the optimal cut while the model trained with the vanilla loss was able to
find it for approximately $65\%$ of the graphs (for 65 out of 100 using the
linear network and for 66 using the ReLU network). In Figure 2 we show two
instances where the model trained with the ”vanilla” loss gets stuck on a sub-
optimal solution while the entropy-regularized one succeeds in finding the
optimal solution. Our experiments show that the regularization term and the
fast/slow mixture scheme that we introduced to achieve our main theoretical
convergence result, see Section 3 and Proposition 4, are potentially useful
for training more realistic models for bigger instances and we leave more
extensive experimental evaluation as an interesting direction for future work.

We note that, similarly to our theoretical results, our sampler in this
experimental section is of the form $e^{\mathrm{score}(s;w)}$, where
$s\in\\{-1,1\\}^{n}$ (here $n$ is the number of nodes in the graph) is a
candidate solution of the Max-Cut problem. The function used is a 3-layer MLP
(see Figure 3). Since the instances that we consider here are small ($n=15$)
we can explicitly compute the density (score) of every solution and use that
to compute the expected gradient. The main message of the current experimental
section is that even for very small instances of Max-Cut (i.e., with 15
nodes), optimizing the vanilla objective is not sufficient and the iteration
gets trapped in local optima. In contrast, our entropy regularized always
manages to find the optimal cut.