$\iota\in\textsf{dom}(\mathcal{M})$ and
$\Sigma\vdash\mathit{e}\texttt{.}\mathsf{f}_{i}:\mathsf{C}$ and
$\textsf{dom}(\Sigma)=\textsf{dom}(\mathcal{M})$. Lemma 8.18 (3) applied to
$\Sigma\vdash\mathit{e}\texttt{.}\mathsf{f}_{i}:\mathsf{C}$ implies
$\Sigma\vdash\mathit{e}:\mathsf{D}$ and
$\mathsf{fields}(\mathsf{D})=\mathsf{C}_{1}\,\mathsf{f}_{1}\texttt{;}\ldots\mathsf{C}_{n}\,\mathsf{f}_{n}\texttt{;}$
and $\mathsf{C}_{i}<:\mathsf{C}$ where $i\in 1..n$. Since
${{\langle{\mathcal{M},\mathit{e}}\rangle}}\,{\Rightarrow}\,{{\langle{\mathcal{M}^{\prime},\iota}\rangle}}$
is a premise we assume
$\Sigma^{\prime}\vdash{\langle{\mathcal{M}^{\prime},\iota}\rangle}:\mathsf{D}$
with $\Sigma\subseteq\Sigma^{\prime}$. Lemma 8.18 (1) and Lemma 8.18 (7) imply
$\Sigma^{\prime}(\iota)<:\mathsf{D}$. Lemma 8.18 (4) allows us to get
$\mathcal{M}^{\prime}(\iota)=\texttt{new}\
\mathsf{C}^{\prime}\texttt{(}\iota_{1},\ldots\iota_{m}\texttt{)}$ with $n\leq
m$ and $\mathsf{C}^{\prime}<:\mathsf{D}$ and
$\Sigma^{\prime}\vdash\iota_{i}:\mathsf{C}_{i}$. So we conclude
$\Sigma^{\prime}\vdash{\langle{\mathcal{M}^{\prime},\iota_{i}}\rangle}:\mathsf{C}$
by rules (t-sub) and (t-conf).

(new)

Lemma 8.18 (1) applied to $\Sigma\vdash{\langle{\mathcal{M},\texttt{new}\
\mathsf{C}\texttt{(}\mathit{e}_{1},\ldots,\mathit{e}_{n}\texttt{)}}\rangle}:\mathsf{D}$
implies $\Sigma\vdash\mathcal{M}(\iota):\Sigma(\iota)$ for all
$\iota\in\textsf{dom}(\mathcal{M})$ and $\Sigma\vdash\texttt{new}\
\mathsf{C}\texttt{(}\mathit{e}_{1},\ldots,\mathit{e}_{n}\texttt{)}:\mathsf{D}$
and $\textsf{dom}(\Sigma)=\textsf{dom}(\mathcal{M})$. Lemma 8.18 (4) applied
to $\Sigma\vdash\texttt{new}\
\mathsf{C}\texttt{(}\mathit{e}_{1},\ldots,\mathit{e}_{n}\texttt{)}:\mathsf{D}$
implies $\mathsf{C}<:\mathsf{D}$ and
$\mathsf{fields}(\mathsf{C})=\mathsf{C}_{1}\,\mathsf{f}_{1}\texttt{;}\ldots\mathsf{C}_{n}\,\mathsf{f}_{n}\texttt{;}$
and $\Sigma\vdash\mathit{e}_{i}:\mathsf{C}_{i}$ for all $i\in 1..n$. Since
${{\langle{\mathcal{M},\mathit{e}_{i}}\rangle}}\,{\Rightarrow}\,{{\langle{\mathcal{M}_{i+1},\iota_{i}}\rangle}}$
is a premise we assume
$\Sigma_{i}\vdash{\langle{\mathcal{M}_{i+1},\iota_{i}}\rangle}:\mathsf{C}_{i}$
for all $i\in 1..n$ with
$\Sigma\subseteq\Sigma_{1}\subseteq\cdots\subseteq\Sigma_{n}$. Lemma 8.18 (1)
and Lemma 8.18 (7) imply $\Sigma_{i}(\iota_{i})<:\mathsf{C}_{i}$ for all $i\in
1..n$. Using rules (t-oid), (t-new) and (t-sub) we derive
$\Sigma_{n}\vdash\texttt{new}\
\mathsf{C}\texttt{(}\iota_{1},\ldots,\iota_{n}\texttt{)}:\mathsf{D}$. We then
conclude
$\Sigma_{n},\iota:\mathsf{D}\vdash{\langle{\mathcal{M}_{n+1},\iota}\rangle}:\mathsf{D}$
by rules (t-oid) and (t-conf).

(invk)

Lemma 8.18 (1) applied to
$\Sigma_{0}\vdash{\langle{\mathcal{M}_{0},\mathit{e}_{0}{\texttt{.}}\mathsf{m}\texttt{(}\mathit{e}_{1},\ldots,\mathit{e}_{n}\texttt{)}}\rangle}:\mathsf{C}$
implies $\Sigma_{0}\vdash\mathcal{M}_{0}(\iota):\Sigma_{0}(\iota)$ for all
$\iota\in\textsf{dom}(\mathcal{M}_{0})$ and
$\Sigma_{0}\vdash\mathit{e}_{0}{\texttt{.}}\mathsf{m}\texttt{(}\mathit{e}_{1},\ldots,\mathit{e}_{n}\texttt{)}:\mathsf{C}$
and $\textsf{dom}(\Sigma_{0})=\textsf{dom}(\mathcal{M}_{0})$. Lemma 8.18 (5)
applied to
$\Sigma_{0}\vdash\mathit{e}_{0}{\texttt{.}}\mathsf{m}\texttt{(}\mathit{e}_{1},\ldots,\mathit{e}_{n}\texttt{)}:\mathsf{C}$
implies $\Sigma_{i}\vdash\mathit{e}_{i}:\mathsf{C}_{i}$ for all $i\in 0..n$
and
${\mathsf{mtype}(\mathsf{C}_{0},\mathsf{m})}=\mathsf{C}_{1}\ldots\mathsf{C}_{n}\rightarrow\mathsf{D}$
with $\mathsf{D}<:\mathsf{C}$. Since
${{\langle{\mathcal{M}_{i},\mathit{e}_{i}}\rangle}}\,{\Rightarrow}\,{{\langle{\mathcal{M}_{i+1},\iota_{i}}\rangle}}$
is a premise we assume
$\Sigma_{i}\vdash{\langle{\mathcal{M}_{i+1},\iota_{i}}\rangle}:\mathsf{C}_{i}$
for all $i\in 0..n$ with $\Sigma_{0}\subseteq\cdots\subseteq\Sigma_{n}$. Lemma
8.18 (1) gives $\Sigma_{i}\vdash\iota_{i}:\mathsf{C}_{i}$ for all $i\in 0..n$.
The typing of the class table implies
${\mathit{x}_{1}{:}\mathsf{C}_{1},\ldots,\mathit{x}_{n}{:}\mathsf{C}_{n},\texttt{this}{:}\mathsf{C}_{0}\vdash\mathit{e}:\mathsf{D}}$.
Lemma 8.19 gives $\Sigma_{n}\vdash\mathit{e}^{\prime}:\mathsf{D}$ where
$\mathit{e}^{\prime}={{{\mathit{e}}[{\iota_{1}}/{\mathit{x}_{1}}]\ldots}[{\iota_{n}}/{\mathit{x}_{n}}]}[{\iota_{0}}/{\texttt{this}}]$.
Using rules (t-sub) and (t-conf) we derive
$\Sigma_{n}\vdash{\langle{\mathcal{M}_{n+1},\mathit{e}^{\prime}}\rangle}:\mathsf{C}$.
Since
${{\langle{\mathcal{M}_{n+1},\mathit{e}^{\prime}}\rangle}}\,{\Rightarrow}\,{{\langle{\mathcal{M}^{\prime},\iota}\rangle}}$
is a premise we conclude
$\Sigma^{\prime}\vdash{\langle{\mathcal{M}^{\prime},\iota}\rangle}:\mathsf{C}$
with $\Sigma_{n}\subseteq\Sigma^{\prime}$.

(fld-up)

Lemma 8.18 (1) applied to
$\Sigma\vdash{\langle{\mathcal{M},\mathit{e}\texttt{.}\mathsf{f}_{i}\texttt{=}\mathit{e}^{\prime}}\rangle}:\mathsf{C}$
implies $\Sigma\vdash\mathcal{M}(\iota):\Sigma(\iota)$ for all
$\iota\in\textsf{dom}(\mathcal{M})$ and
$\Sigma\vdash\mathit{e}\texttt{.}\mathsf{f}_{i}\texttt{=}\mathit{e}^{\prime}:\mathsf{C}$
and $\textsf{dom}(\Sigma)=\textsf{dom}(\mathcal{M})$. Lemma 8.18 (6) applied
to
$\Sigma\vdash\mathit{e}\texttt{.}\mathsf{f}_{i}\texttt{=}\mathit{e}^{\prime}:\mathsf{C}$
implies $\Sigma\vdash\mathit{e}:\mathsf{D}$ and
$\mathsf{fields}(\mathsf{D})=\mathsf{C}_{1}\,\mathsf{f}_{1}\texttt{;}\ldots\mathsf{C}_{n}\,\mathsf{f}_{n}\texttt{;}$
and $\Sigma\vdash\mathit{e}^{\prime}:\mathsf{C}_{i}$ and
$\mathsf{C}_{i}<:\mathsf{C}$. Since
${{\langle{\mathcal{M},\mathit{e}}\rangle}}\,{\Rightarrow}\,{{\langle{\mathcal{M}^{\prime},\iota}\rangle}}$
and
${{\langle{\mathcal{M}^{\prime},\mathit{e}^{\prime}}\rangle}}\,{\Rightarrow}\,{{\langle{\mathcal{M}^{\prime\prime},\iota^{\prime}}\rangle}}$
are premises we assume
$\Sigma^{\prime}\vdash{\langle{\mathcal{M}^{\prime},\iota}\rangle}:\mathsf{D}$
and
$\Sigma^{\prime\prime}\vdash{\langle{\mathcal{M}^{\prime\prime},\iota^{\prime}}\rangle}:\mathsf{C}_{i}$,
with $\Sigma\subseteq\Sigma^{\prime}\subseteq\Sigma^{\prime\prime}$. Notice
that $\mathcal{M}^{\prime\prime}(\iota)$ and
$\mathcal{M}^{\prime\prime}_{[\iota.i=\iota^{\prime}]}(\iota)$ have the same
types for all $\iota$ by construction. We conclude
$\Sigma^{\prime\prime}\vdash{\langle{\mathcal{M}^{\prime\prime}_{[\iota.i=\iota^{\prime}]},\iota^{\prime}}\rangle}:\mathsf{C}_{i}$.

Proof of ($\exists$p): All the closed expressions appear as conclusions in the
reduction rules.

Proof of ($\forall$p): Since the only values are configurations with object
identifiers it is easy to verify that the premises of the reduction rules are
satisfied, being the conditions on memory and object identifiers assured by
the typing rules. ∎

##  9\. Concluding discussions

The big-step style can be useful for abstracting details or directly deriving
the implementation of an interpreter. However, reasoning on properties
involving infinite computations, such as the soundness of a type system, is
non-trivial, because standard big-step semantics is able only to capture
finite computations, hence it cannot distinguish between stuck and infinite
ones.

In this paper, we address this problem, providing a systematic analysis of
big-step semantics. The first, and fundamental, methodological feature of our
analysis is that we want to be _independent from specific languages_ ,
developing an abstract study of big-step semantics in itself. Therefore, we
provide a definition of what a big-step semantics is, so our results will be
applicable, as we show by several examples, to all concrete big-step semantics
matching our definition.

A second important building block of our approach is that we take seriously
the fact that big-step rules implicitly define an _evaluation algorithm_.
Indeed, we make such intuition formal by showing that starting from the rules
we can define a transition relation on incomplete derivations, abstractly
modeling such evaluation algorithm. Relying on this transition relation, we
are able to define computations in the big-step semantics in the usual way, as
possibly infinite sequences of transition steps; thus we can distinguish
converging, diverging and stuck computations, even though big-step rules only
define convergence. This shows that diverging and stuck computations are, in a
sense, implicit in standard big-step rules, and the transition relation makes
them explicit.

Finally, the third feature of our approach is that we provide _constructions_
that, starting from a usual big-step semantics, produce an extended one where
the distinction between diverging and stuck computation is explicit. Such
constructions show that we can distinguish stuckness and divergence directly
by a big-step semantics, without resorting to a transition relation: we rely
on the above described transition relation on incomplete derivations only to
prove that the constructions are correct. Corules are crucial to define
extended big-step semantics precisely modelling divergence just as a special
result, thus avoiding the redundancy introduced by traces.

Building on this systematic study, we show how one can reason about soundness
of a predicate directly on a big-step semantics. To this end, we design proof
techniques for two flavours of soundness, based on sufficient conditions on
big-step rules.

###  9.1. Related work

The research presented in this paper follows a stream of work dating back to
Cousot and Cousot (1992), who proposed a stratified approach, investigated by
Leroy and Grall (2009) as well, with a separate judgment for divergence,
defined coinductively. In this way, however, there is no unique formal
definition of the behaviour of the modelled system. An alternative
possibility, also investigated by Leroy and Grall (2009), is to interpret
coinductively the standard big-step rules (_coevaluation_). Unfortunately,
coevaluation is non-deterministic, allowing the derivation of spurious
judgements, and, thus, may fail to correctly capture the infinite behavior of
a configuration: a diverging term, such as $\Omega$, evaluates to any value,
hence it cannot be properly distinguished from converging terms. Furthermore,
in coevaluation there are still configurations, such as $\Omega\,(0\,0)$, for
which no judgment can be derived, here because no judgment can be derived for
the subterm $0\,0$; basically, this is due to the fact that divergence of a
premise should be propagated and this cannot be correctly handled by
coevaluation as divergence is not explicitly modelled.

_Pretty big-step semantics_ by Charguéraud (2013) handles the issue of
duplication of meta-rules by a unified judgment with a unique set of
(meta-)rules and divergence modelled by a special value. Rules are interpreted
coinductively, hence they allow the derivation of spurious judgements, but,
thanks to the use of a special value for divergence and the particular
structure of rules, they can solve most of the issues of coevaluation.
However, this particular structure of rules is not as natural as usual big-
step rules and, more importantly, it requires the introduction of new specific
syntactic forms representing intermediate computation steps, as in small-step
semantics, hence making the big-step semantics less abstract. This may be a
problem, for instance, when proving soundness of a type system, as such
intermediate configurations may be ill-typed.

Poulsen and Mosses (2017) subsequently present _flag-based big-step semantics_
, which further streamlines the approach by combining it with the M-SOS
technique (modular structural operational semantics), thereby reducing the
number of (meta-)rules and premises, avoiding the need for intermediate
configurations. The key idea is to extend configurations and results by flags
explicitly modelling convergence and divergence, used to properly handle
divergence propagation. To model divergence, they interpret rules
coinductively, hence they allow the derivation of spurious judgements.

Differently from all the previously cited papers, which consider specific
examples, the work by Ager (2004) shares with us the aim of providing a
generic construction to model non-termination, basing on an arbitrary big-step
semantics. Ager considers a big-step judgement of shape $\rho\vdash
t\Downarrow v$ where $\rho$ is an environment, $t$ a syntactic term and $v$ a
final value, and values, environments and the signature for terms are left
unspecified. Then, given a big-step semantics, he describes a method to
extract an abstract machine from it, which models a proof-search algorithm. In
this way, converging, diverging and stuck computations are distinguished. This
approach is somehow similar to our transition relation on partial evaluation
trees, even tough a different style is used: we have no syntactic components
and the transition system we propose is directly defined on evaluation trees
and corresponds to a partial order on them, modelling refinement. Moreover,
Ager’s notion of big-step semantics is not fully formal, in particular, it is
not clear whether he works with plain rules or meta-rules.

Another piece of work whose aim is to define a general framework for
operational semantics specification is the one by Bodin et al. (2019) on
_skeletal semantics_. Here the key idea is to specify the semantics of a
language by a set of skeletons, one for each syntactic construct, which
describe how to evaluate each of them. Skeletons are very much like big-step
rules, indeed they can be regarded as an ad-hoc syntax for specifying them.
This syntax is quite unusual, but probably better suited for the Coq
implementation which the framework comes with. This approach is not
specifically tailored for big-step semantics: a skeletal specification can
give rise to semantics in different styles, such as big-step, small-step or
abstract machines. However, given the similarity between skeletons and big-
step rules, it may be possible to adapt the proof technique we propose to this
setting, but this is matter for future work.

Ancona et al. (2017b) firstly show that with corules one can define a unified
big-step judgment with a unique set of rules avoiding spurious evaluations.
This can be seen as _constrained coevaluation_. Indeed, corules add
constraints on the infinite derivations to filter out spurious results, so
that, for diverging terms, it is only possible to get $\infty$ as result. This
is extended to include observations as traces by Ancona et al. (2018). A
further step is done by Ancona et al. (2020), where observations are modelled
by an arbitrary monoid and a variant of the construction described in Section
6 is considered.

Other proposals, by Owens et al. (2016); Amin and Rompf (2017), are inspired
by _definitional interpreters_ (Reynolds, 1972), based on a step-indexed
approach (a.k.a.“fuel”-based semantics) where computations are approximated to
some finite amount of steps (typically with a counter); in this way divergence
can be modeled by induction. Owens et al. (2016) investigates functional big-
step semantics for proving by induction compiler correctness. Amin and Rompf
(2017) explore inductive proof strategies for type soundness properties for
the polymorphic type systems $F_{<:}$, and equivalence with small-step
semantics. An inductive proof of type soundness for the big-step semantics of
a Java-like language is proposed by Ancona (2014).

Coinductive trace semantics in big-step style have been studied by Nakata and
Uustalu (2009, 2010a, 2010b). Their investigation started with the semantics
of an imperative While language with no I/O (Nakata and Uustalu, 2009), where
traces are possibly infinite sequences of states; semantic rules are all
coinductive and define two mutually dependent judgments. Based on such a
semantics, they define a Hoare logic (Nakata and Uustalu, 2010a). They provide
a constructive theory and metatheory, together with a Coq formalization of
their results. Differently from our approach, weak bisimilarity between traces
is needed for proving that programs exhibit equivalent observable behaviors.
This is due to the fact that “silent effects” (that is, non-observable
internal steps) must be explicitly represented to guarantee guardedness
conditions which ensure productivity of corecursive definitions. This is a
natural consequence of having computable definitions. By using corules, we can
avoid bisimilarity, accepting an approach which is not fully constructive.

This semantics has been subsequently extended with interactive I/O (Nakata and
Uustalu, 2010b), by exploiting the notion of resumption monad: a tree
representing possible runs of a program to model its non-deterministic
behavior due to input values. Also in this case a big-step trace semantics is
defined with two mutually recursive coinductive judgments, and weak
bisimilarity is needed; however, the definition of the observational
equivalence is more involved, since it requires nesting inductive definitions
in coinductive ones. A generalised notion of resumption has been introduced
later by Piróg and Gibbons (2014) in a category-theoretic and coalgebraic
context.

Danielsson (2012), inspired by Leroy and Grall (2009), relying on the
coinductive partiality monad, defines big-step semantics for $\lambda$-calculi
and virtual machines as total, computable functions able to capture
divergence.

The resumption monad of Nakata and Uustalu (2010b) and the partiality monad of
Danielsson (2012) are inspired by the seminal work of Capretta (2005) on the
_delay monad_ , where coinductive types are exploited to model infinite
computations by means of a type constructor for partial elements, which allows
the formal definition of convergence and divergence and a type-theoretic
representation of general recursive functions; this type constructor is proved
to constitute a strong monad, upon which subsequent related papers (Abel and
Chapman, 2014; McBride, 2015; Chapman et al., 2019) elaborated to define other
monads for managing divergence. In particular, McBride (2015) has proposed a
more general approach based on a free monad for which the delay monad is an
instantiation obtained through a monad morphism. All these proposals are based
on the step-indexed approach.

More recently, interaction trees (ITrees) (Xia et al., 2020) have been
presented as a coinductive variant of free monads with the main aim of
defining the denotational semantics for effectful and possibly nonterminating
computations, to allow compositional reasoning for mutually recursive
components of an interactive system, with fully mechanized proofs in Coq.
Interaction trees are coinductively defined trees which directly support a
more general fixpoint combinator which does need a step-indexed approach, as
happens for the general monad of McBride. A Tau constructor is introduced to
represent a silent step of computation, to express silently diverging
computations without violating Coq’s guardedness condition; as a consequence,
a generic definition of weak bisimulation on ITrees is required to remove any
finite number of Taus, similarly as what happens in the approach of Nakata and
Uustalu.

###  9.2. Future work

There are several directions for further research. A first direction is to
study other approaches to model divergence in big-step semantics using our
general meta-theory, that is, defining yet other constructions, such as adding
a counter and timeout, as done by Owens et al. (2016); Amin and Rompf (2017),
or adding flags, as done by Poulsen and Mosses (2017). This would provide a
general account of these approaches, allowing to study their properties in
general, abstracting away particular features of concrete languages. A further
direction is to consider other computational models such as probabilistic
computations, which are quite difficult to model in big-step style, as shown
by Dal Lago and Zorzi (2012).

Concerning proof techniques for soundness, we also plan to compare our proof
technique with the standard one for small-step semantics: if a predicate
satisfies progress and subject reduction with respect to a small-step
semantics, does it satisfy our soundness conditions with respect to an
equivalent big-step semantics? To formally prove such a statement, the first
step will be to express equivalence between small-step and big-step semantics,
and such equivalence has to be expressed at the level of big-step rules, as it
needs to be extendible to stuck and infinite computations. Note that, as a by-
product, this will provide us with a proof technique to show equivalence
between small-step and big-step semantics. Ancona et al. (2020) make a first
attempt to express such an equivalence for a more restrictive class of big-
step semantics. On the other hand, the converse does not hold, as shown by the
examples in Section 8.2 and Section 8.4.

Furthermore, it would be interesting to extend such techniques for soundness
to big-step semantics with observations, taking inspiration from type and
effect systems (Marino and Millstein, 2009; Tate, 2013).

Last but not least, to support reasoning by our framework on concrete
examples, such as those in Section 8, it is desirable to have a mechanisation
of our meta-theory and related techniques. A necessary preliminary step in
this direction is to provide support for corules in proof assistants. An Agda
library supporting (generalised) inference systems is described by Ciccone et
al. (2021) and can be found at https://github.com/LcicC/inference-systems-
agda. Moreover, in the paper we lazily relied on the usual setting of
classical logic (even though we try not to abuse of it), however, towards a
formalisation, we will have to carefully rearrange definitions and proofs to
fit the logic of the choosen proof assistant.

###### Acknowledgements.

Special thanks go to Elena Zucca, Mariangiola Dezani-Ciancaglini and Viviana
Bono for collaborating on this work with many interesting discussions and
useful suggestions, which have greatly improved the paper.

## References

  * (1)
  * Abadi and Cardelli (1996) Martín Abadi and Luca Cardelli. 1996.  _A Theory of Objects_.  Springer.  https://doi.org/10.1007/978-1-4419-8598-9
  * Abel and Chapman (2014) Andreas Abel and James Chapman. 2014.  Normalization by Evaluation in the Delay Monad: A Case Study for Coinduction via Copatterns and Sized Types. In _Proceedings 5th Workshop on Mathematically Structured Functional Programming, MSFP@ETAPTS 2014_ _(Electronic Proceedings in Theoretical Computer Science, Vol. 153)_ , Paul Levy and Neel Krishnaswami (Eds.). 51–67.  https://doi.org/10.4204/EPTCS.153.4
  * Aczel (1977) Peter Aczel. 1977\.  An Introduction to Inductive Definitions.  In _Handbook of Mathematical Logic_ , Jon Barwise (Ed.). Studies in Logic and the Foundations of Mathematics, Vol. 90. Elsevier, 739 – 782.
  * Ager (2004) Mads Sig Ager. 2004\.  From Natural Semantics to Abstract Machines. In _Logic-Based Program Synthesis and Transformation - 14th International Symposium, LOPSTR 2004_ _(Lecture Notes in Computer Science, Vol. 3573)_ , Sandro Etalle (Ed.). Springer, Berlin, 245–261.  https://doi.org/10.1007/11506676_16
  * Amin and Rompf (2017) Nada Amin and Tiark Rompf. 2017.  Type Soundness Proofs with Definitional Interpreters. In _The 44th Annual ACM Symposium on Principles of Programming Languages, POPL’17_ , Giuseppe Castagna and Andrew D. Gordon (Eds.). ACM Press, New York, 666–679.  https://doi.org/10.1145/3009837
  * Ancona (2014) Davide Ancona. 2014\.  How to Prove Type Soundness of Java-like Languages without Forgoing Big-Step Semantics. In _Proceedings of 16th Workshop on Formal Techniques for Java-like Programs, FTfJP’14_ , David J. Pearce (Ed.). ACM Press, New York, 1:1–1:6.  https://doi.org/10.1145/2635631.2635846
  * Ancona et al. (2020) Davide Ancona, Francesco Dagnino, Jurriaan Rot, and Elena Zucca. 2020.  A big step from finite to infinite computations.  _Science of Computer Programming_ 197 (2020), 102492.  https://doi.org/10.1016/j.scico.2020.102492
  * Ancona et al. (2017a) Davide Ancona, Francesco Dagnino, and Elena Zucca. 2017a.  Generalizing Inference Systems by Coaxioms. In _Programming Languages and Systems - 26th European Symposium on Programming, ESOP 2017_ _(Lecture Notes in Computer Science, Vol. 10201)_ , Hongseok Yang (Ed.). Springer, Berlin, 29–55.  https://doi.org/10.1007/978-3-662-54434-1_2
  * Ancona et al. (2017b) Davide Ancona, Francesco Dagnino, and Elena Zucca. 2017b.  Reasoning on Divergent Computations with Coaxioms.  _Proceedings of ACM on Programming Languages_ 1, OOPSLA (2017), 81:1–81:26.  https://doi.org/10.1145/3133905
  * Ancona et al. (2018) Davide Ancona, Francesco Dagnino, and Elena Zucca. 2018\.  Modeling Infinite Behaviour by Corules. In _32nd European Conference on Object-Oriented Programming, ECOOP 2018_ _(LIPIcs, Vol. 109)_ , Todd D. Millstein (Ed.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, Dagstuhl, 21:1–21:31.  https://doi.org/10.4230/LIPIcs.ECOOP.2018.21
  * Barbanera et al. (1995) Franco Barbanera, Mariangiola Dezani-Ciancaglini, and Ugo de’Liguoro. 1995.  Intersection and Union Types: Syntax and Semantics.  _Information and Computation_ 119, 2 (1995), 202–230.  https://doi.org/10.1006/inco.1995.1086
  * Barendregt et al. (2013) Hendrik Pieter Barendregt, Wil Dekkers, and Richard Statman. 2013\.  _Lambda Calculus with Types_.  Cambridge University Press, Cambridge.
  * Bettini et al. (2018) Lorenzo Bettini, Viviana Bono, Mariangiola Dezani-Ciancaglini, Paola Giannini, and Betti Venneri. 2018\.  Java & Lambda: a Featherweight Story.  _Logical Methods in Computer Science_ 14, 3 (2018), 24 pages.  https://doi.org/10.23638/LMCS-14(3:17)2018
  * Bodin et al. (2019) Martin Bodin, Philippa Gardner, Thomas P. Jensen, and Alan Schmitt. 2019.  Skeletal semantics and their interpretations.  _Proceedings of ACM on Programming Languages_ 3, POPL (2019), 44:1–44:31.  https://doi.org/10.1145/3290357
  * Capretta (2005) Venanzio Capretta. 2005\.  General Recursion via Coinductive Types.  _Logical Methods in Computer Science_ 1, 2 (2005), 28 pages.  https://doi.org/10.2168/LMCS-1(2:1)2005
  * Capretta et al. (2009) Venanzio Capretta, Tarmo Uustalu, and Varmo Vene. 2009\.  Corecursive Algebras: A Study of General Structured Corecursion. In _Formal Methods: Foundations and Applications, 12th Brazilian Symposium on Formal Methods, SBMF 2009_ _(Lecture Notes in Computer Science, Vol. 5902)_ , Marcel Vinícius Medeiros Oliveira and Jim Woodcock (Eds.). Springer, 84–100.  https://doi.org/10.1007/978-3-642-10452-7_7
  * Chapman et al. (2019) James Chapman, Tarmo Uustalu, and Niccolò Veltri. 2019\.  Quotienting the delay monad by weak bisimilarity.  _Mathematical Structures in Computer Scienc_ 29, 1 (2019), 67–92.  https://doi.org/10.1017/S0960129517000184
  * Charguéraud (2013) Arthur Charguéraud. 2013\.  Pretty-Big-Step Semantics. In _Programming Languages and Systems - 22nd European Symposium on Programming, ESOP 2013_ _(Lecture Notes in Computer Science, Vol. 7792)_ , Matthias Felleisen and Philippa Gardner (Eds.). Springer, Berlin, 41–60.  https://doi.org/10.1007/978-3-642-37036-6_3
  * Ciccone et al. (2021) Luca Ciccone, Francesco Dagnino, and Elena Zucca. 2021\.  Flexible Coinduction in Agda. In _12th International Conference on Interactive Theorem Proving, ITP 2021_ _(LIPIcs, Vol. 193)_ , Liron Cohen and Cezary Kaliszyk (Eds.). Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 13:1–13:19.  https://doi.org/10.4230/LIPIcs.ITP.2021.13
  * Courcelle (1983) Bruno Courcelle. 1983\.  Fundamental Properties of Infinite Trees.  _Theoretical Computer Science_ 25 (1983), 95–169.  https://doi.org/10.1016/0304-3975(83)90059-2
  * Cousot and Cousot (1992) Patrick Cousot and Radhia Cousot. 1992.  Inductive Definitions, Semantics and Abstract Interpretations. In _The 19th Annual ACM Symposium on Principles of Programming Languages, POPL’92_ , Ravi Sethi (Ed.). ACM Press, New York, 83–94.  https://doi.org/10.1145/143165.143184
  * Dagnino (2019) Francesco Dagnino. 2019\.  Coaxioms: flexible coinductive definitions by inference systems.  _Logical Methods in Computer Science_ 15, 1 (2019).  https://doi.org/10.23638/LMCS-15(1:26)2019
  * Dagnino (2021a) Francesco Dagnino. 2021a.  _Flexible Coinduction_.  Ph.D. Dissertation. DIBRIS, University of Genova.  https://web.archive.org/web/20210214063202id_/https://iris.unige.it/retrieve/handle/11567/1035050/502494/phdunige_3767524.pdf
  * Dagnino (2021b) Francesco Dagnino. 2021b.  Foundations of regular coinduction.  _Logical Methods in Computer Science_ 17 (2021).  Issue 4. https://doi.org/10.46298/lmcs-17(4:2)2021
  * Dagnino et al. (2020a) Francesco Dagnino, Davide Ancona, and Elena Zucca. 2020a.  Flexible coinductive logic programming.  _Theory and Practice of Logic Programming_ 20, 6 (2020), 818–833.  https://doi.org/10.1017/S147106842000023X Issue for ICLP 2020.
  * Dagnino et al. (2020b) Francesco Dagnino, Viviana Bono, Elena Zucca, and Mariangiola Dezani-Ciancaglini. 2020b.  Soundness Conditions for Big-Step Semantics. In _Programming Languages and Systems - 29th European Symposium on Programming, ESOP 2020_ _(Lecture Notes in Computer Science, Vol. 12075)_ , Peter Müller (Ed.). Springer, 169–196.  https://doi.org/10.1007/978-3-030-44914-8_7
  * Dal Lago and Zorzi (2012) Ugo Dal Lago and Margherita Zorzi. 2012.  Probabilistic operational semantics for the lambda calculus.  _RAIRO Theoretical Informatics and Applications_ 46, 3 (2012), 413–450.  https://doi.org/10.1051/ita/2012012
  * Danielsson (2012) Nils Anders Danielsson. 2012\.  Operational Semantics using the Partiality Monad. In _Proceedings of the 17th ACM International Conference on Functional Programming, ICFP 2012_ , Peter Thiemann and Robby Bruce Findler (Eds.). ACM Press, New York, 127–138.  https://doi.org/10.1145/2364527.2364546
  * De Nicola and Hennessy (1984) Rocco De Nicola and Matthew Hennessy. 1984.  Testing Equivalences for Processes.  _Theoretical Computer Science_ 34, 1 (1984), 83 – 133.  https://doi.org/10.1016/0304-3975(84)90113-0
  * Dezani-Ciancaglini et al. (1998) Mariangiola Dezani-Ciancaglini, Ugo de’Liguoro, and Adolfo Piperno. 1998\.  A Filter Model for Concurrent lambda-Calculus.  _SIAM Journal of Computing_ 27, 5 (1998), 1376–1419.  https://doi.org/10.1137/S0097539794275860
  * Gosling et al. (2014) James Gosling, Bill Joy, Guy L. Steele, Gilad Bracha, and Alex Buckley. 2014.  _The Java Language Specification, Java SE 8 Edition_ (1st ed.).  Addison-Wesley Professional, Boston.
  * Grudzinski (2000) Grzegorz Grudzinski. 2000\.  A Minimal System of Disjunctive Properties for Strictness Analysis. In _ICALP Workshops_ , José D. P. Rolim, Andrei Z. Broder, Andrea Corradini, Roberto Gorrieri, Reiko Heckel, Juraj Hromkovic, Ugo Vaccaro, and J. B. Wells (Eds.). Carleton Scientific, Waterloo, Ontario, Canada, 305–322.
  * Igarashi and Nagira (2007) Atsushi Igarashi and Hideshi Nagira. 2007.  Union Types for Object-Oriented Programming.  _Journal of Object Technology_ 6, 2 (2007), 47–68.  https://doi.org/10.5381/jot.2007.6.2.a3
  * Igarashi et al. (2001) Atsushi Igarashi, Benjamin C. Pierce, and Philip Wadler. 2001\.  Featherweight Java: A Minimal Core Calculus for Java and GJ.  _ACM Transactions on Programming Languages and Systems_ 23, 3 (2001), 396–450.  https://doi.org/10.1145/503502.503505
  * Kahn (1987) Gilles Kahn. 1987\.  Natural Semantics. In _4th Annual Symposium on Theoretical Aspects of Computer Science, STACS’87_ _(Lecture Notes in Computer Science, Vol. 247)_ , Franz-Josef Brandenburg, Guy Vidal-Naquet, and Martin Wirsing (Eds.). Springer, Berlin, 22–39.  https://doi.org/10.1007/BFb0039592
  * Leroy and Grall (2009) Xavier Leroy and Hervé Grall. 2009.  Coinductive big-step operational semantics.  _Information and Computation_ 207, 2 (2009), 284–304.  https://doi.org/10.1016/j.ic.2007.12.004
  * Marino and Millstein (2009) Daniel Marino and Todd D. Millstein. 2009.  A generic type-and-effect system. In _Proceedings of TLDI’09: ACM International Workshop on Types in Languages Design and Implementation_ , Andrew Kennedy and Amal Ahmed (Eds.). ACM Press, 39–50.  https://doi.org/10.1145/1481861.1481868
  * McBride (2015) Conor McBride. 2015\.  Turing-Completeness Totally Free. In _Mathematics of Program Construction - 12th International Conference, MPC 2015_ _(Lecture Notes in Computer Science, Vol. 9129)_ , Ralf Hinze and Janis Voigtländer (Eds.). Springer, 257–275.  https://doi.org/10.1007/978-3-319-19797-5_13
  * Milner (1978) Robin Milner. 1978\.  A Theory of Type Polymorphism in Programming.  _J. Comput. System Sci._ 17, 3 (1978), 348–375.  https://doi.org/10.1016/0022-0000(78)90014-4
  * Nakata and Uustalu (2009) Keiko Nakata and Tarmo Uustalu. 2009.  Trace-Based Coinductive Operational Semantics for While. In _Theorem Proving in Higher Order Logics, 22nd International Conference, TPHOLs 2009_ _(Lecture Notes in Computer Science, Vol. 5674)_ , Stefan Berghofer, Tobias Nipkow, Christian Urban, and Makarius Wenzel (Eds.). Springer, 375–390.  https://doi.org/10.1007/978-3-642-03359-9_26
  * Nakata and Uustalu (2010a) Keiko Nakata and Tarmo Uustalu. 2010a.  A Hoare Logic for the Coinductive Trace-Based Big-Step Semantics of While. In _Programming Languages and Systems - 19th European Symposium on Programming, ESOP 2010_ _(Lecture Notes in Computer Science, Vol. 6012)_ , Andrew D. Gordon (Ed.). Springer, 488–506.  https://doi.org/10.1007/978-3-642-11957-6_26
  * Nakata and Uustalu (2010b) Keiko Nakata and Tarmo Uustalu. 2010b.  Resumptions, Weak Bisimilarity and Big-Step Semantics for While with Interactive I/O: An Exercise in Mixed Induction-Coinduction. In _Proceedings 7th Workshop on Structural Operational Semantics, SOS 2010_ _(Electronic Proceedings in Theoretical Computer Science, Vol. 32)_ , Luca Aceto and Pawel Sobocinski (Eds.). 57–75.  https://doi.org/10.4204/EPTCS.32.5
  * Owens et al. (2016) Scott Owens, Magnus O. Myreen, Ramana Kumar, and Yong Kiam Tan. 2016.  Functional Big-Step Semantics. In _Programming Languages and Systems - 25th European Symposium on Programming, ESOP 2016_ _(Lecture Notes in Computer Science, Vol. 9632)_ , Peter Thiemann (Ed.). Springer, Berlin, 589–615.  https://doi.org/10.1007/978-3-662-49498-1_23
  * Pierce (2002) Benjamin C. Pierce. 2002\.  _Types and programming languages_.  MIT Press, Cambridge, Massachusetts.
  * Piróg and Gibbons (2014) Maciej Piróg and Jeremy Gibbons. 2014.  The Coinductive Resumption Monad. In _Proceedings of the 30th Conference on the Mathematical Foundations of Programming Semantics, MFPS 2014_ _(Electronic Notes in Theoretical Computer Science, Vol. 308)_. Elsevier, 273–288.  https://doi.org/10.1016/j.entcs.2014.10.015
  * Plotkin (1981) Gordon D. Plotkin. 1981\.  _A structural approach to operational semantics_.  Technical Report. Aarhus University.
  * Plotkin (2004) Gordon D. Plotkin. 2004\.  A Structural Approach to Operational Semantics.  _Journal of Logic and Algebraic Programming_ 60-61 (2004), 17–139.
  * Poulsen and Mosses (2017) Casper Bach Poulsen and Peter D. Mosses. 2017.  Flag-based Big-step Semantics.  _Journal of Logic and Algebraic Methods in Programming_ 88 (2017), 174–190.  https://doi.org/10.1016/j.jlamp.2016.05.001
  * Reynolds (1972) John C. Reynolds. 1972\.  Definitional interpreters for higher-order programming languages. In _ACM’72, Proceedings of the ACM annual conference_ , Vol. 2. ACM Press, New York, 717–740.
  * Rutten (2000) Jan J. M. M. Rutten. 2000\.  Universal coalgebra: a theory of systems.  _Theoretical Computer Science_ 249, 1 (2000), 3–80.  https://doi.org/10.1016/S0304-3975(00)00056-6
  * Sangiorgi (2011) Davide Sangiorgi. 2011\.  _Introduction to Bisimulation and Coinduction_.  Cambridge University Press, USA.
  * Tate (2013) Ross Tate. 2013\.  The sequential semantics of producer effect systems. In _The 40th Annual ACM Symposium on Principles of Programming Languages, POPL’13_ , Roberto Giacobazzi and Radhia Cousot (Eds.). ACM Press, 15–26.  https://doi.org/10.1145/2429069.2429074
  * Wright and Felleisen (1994) Andrew K. Wright and Matthias Felleisen. 1994.  A Syntactic Approach to Type Soundness.  _Information and Computation_ 115, 1 (1994), 38–94.  https://doi.org/10.1006/inco.1994.1093
  * Xia et al. (2020) Li-yao Xia, Yannick Zakowski, Paul He, Chung-Kil Hur, Gregory Malecha, Benjamin C. Pierce, and Steve Zdancewic. 2020.  Interaction trees: representing recursive and impure programs in Coq.  _Proceedings of ACM on Programming Languages_ 4, The 47th Annual ACM Symposium on Principles of Programming Languages, POPL’20 (2020), 51:1–51:32.  https://doi.org/10.1145/3371119


# ML-Based Approach for NFL Defensive Pass Interference Prediction Using GPS
Tracking Data

Arian Skoki  University of Rijeka, Faculty of Engineering, Department of
Computer Engineering, Rijeka 51000, Croatia
Email: {askoki, jlerga<EMAIL_ADDRESS>Jonatan Lerga  University of
Rijeka, Faculty of Engineering, Department of Computer Engineering, Rijeka
51000, Croatia
Email: {askoki, jlerga<EMAIL_ADDRESS>University of Rijeka, Center for
Artificial Intelligence and Cybersecurity, Rijeka 51000, Croatia  Ivan
Štajduhar  University of Rijeka, Faculty of Engineering, Department of
Computer Engineering, Rijeka 51000, Croatia
Email: {askoki, jlerga<EMAIL_ADDRESS>University of Rijeka, Center for
Artificial Intelligence and Cybersecurity, Rijeka 51000, Croatia

###### Abstract

Defensive Pass Interference (DPI) is one of the most impactful penalties in
the NFL. DPI is a spot foul, yielding an automatic first down to the team in
possession. With such an influence on the game, referees have no room for a
mistake. It is also a very rare event, which happens 1-2 times per 100 pass
attempts. With technology improving and many IoT wearables being put on the
athletes to collect valuable data, there is a solid ground for applying
machine learning (ML) techniques to improve every aspect of the game. The work
presented here is the first attempt in predicting DPI using player tracking
GPS data. The data we used was collected by NFL’s Next Gen Stats throughout
the 2018 regular season. We present ML models for highly imbalanced time-
series binary classification: LSTM, GRU, ANN, and Multivariate LSTM-FCN.
Results showed that using GPS tracking data to predict DPI has limited
success. The best performing models had high recall with low precision which
resulted in the classification of many false positive examples. Looking
closely at the data confirmed that there is just not enough information to
determine whether a foul was committed. This study might serve as a filter for
multi-step pipeline for video sequence classification which could be able to
solve this problem.

###### Index Terms:

Defensive Pass Interference, GPS, prediction, time-series, NFL

##  I Introduction

American Football is the most popular sport in the United States. National
Football League (NFL) is a professional American football league that consists
of 32 teams, divided in two conferences and many divisions. Each team plays a
regular part of the season and then, if successful, proceeds to the playoffs.
On the field, there are 11 players in every team and the goal of the game is
to win as many yards as possible and ultimately score more points than the
other team. An American football field is 100 yards (91.44 m) long and 160
feet (48.8 m) wide. Points are awarded on touchdown (6 points), field goal (3
points), safety (2 points) and try after touchdown (1-2 points)
111https://operations.nfl.com/the-rules/2020-nfl-rulebook/ (last accessed on
26. May 2021).

One of the biggest game-changers in NFL is the defensive pass interference
(DPI) penalty which applies from the time the ball is thrown until the ball is
touched. The penalty for DPI is an automatic first down at the spot of the
foul. The official rule for pass interference is any act performed by a player
more than one yard beyond the line of scrimmage which significantly hinders an
eligible player’s opportunity to catch the ball. Pass interference can only
occur when a forward pass is thrown from behind the line of scrimmage,
regardless of whether the pass is legal or illegal, or whether it crosses the
line 222https://operations.nfl.com/the-rules/nfl-video-rulebook/defensive-
pass-interference/ (last accessed on 26. May 2021).

NFL Data Bowl 2019 provided data of predicted catch probabilities. This also
opened up an opportunity to analyse $\approx$6,000 catch plays from a sample
of 91 games. Peter Wu and Brendon Gu found the bimodal shape of the defensive
pass interference (DPI) distributions, which could be a result of differing
standards for what a DPI entails [1]. In their paper ”DIRECT: A Two-Level
System for Defensive Pass Interference Rooted in Repeatability,
Enforceability, Clarity, and Transparency”, they have presented a new approach
for lowering the influence of DPI on the game [1]. In the proposed paper, only
the obvious fouls, where the defender had no intention to play the ball, could
be penalised in a spot foul.

In recent years, data analytics in NFL has become quite important, and more
and more data is made publicly available for enthusiasts and scientists to
explore. This year’s Data Bowl (2021), among other questions, asked if there
is any way player tracking data can be used to predict whether or not specific
penalties - for example, defensive pass interference - will be called? This
paper is, to the best of our knowledge, the first attempt in predicting DPI
using tracking (GPS) data.

##  II Materials and Methods

###  II-A Data Acquisition

Data was acquired from ”NFL Big Data Bowl 2021” which was hosted on Kaggle
333https://www.kaggle.com/c/nfl-big-data-bowl-2021/. The data was provided for
competition, non-commercial and academic usage. The 2021 Big Data Bowl data
contains player tracking, play, game, and player level information for all
possible passing plays during the 2018 regular season. This means that 17
weeks of a typical NFL season contain only 259 actions that resulted in a DPI,
which is 1.46% of all actions (17,703). Such a data set is highly imbalanced,
which can be compared with the problem of card fraud detection classification
[2].

###  II-B Data Processing

The raw data set contains the information concerning the majority of players
involved in that particular action play. Every play is divided into timestamp
segments. Every timestamp contains tracking data of all defenders, attackers,
and the ball. This can give a maximum of 23 records in a single timestamp.
Keeping in mind the amount of data, that is simply too much information for a
model to generalise on. A model would have to learn the change of patterns for
each variable (distance, speed, acceleration, etc.) for every player and
additionally, a relationship of these variables between the players. DPI
occurs between players competing for the ball. Therefore, the focus in
processing should be on extracting the most relevant players and ball
information from every given play.

An example of DPI play is shown on image 1. Blue and red circles represent the
home and the away team respectively. The ball is depicted with a green circle,
and the blue team has possession. The width of the pitch is represented on the
y-axis. Height is subtracted from the original 120 yards to 50 yards, to
provide better visualisation of this particular play. DPI can occur from the
moment the ball is thrown forward by a quarterback (QB) and that moment is
represented in image 1(a). In the image 1(b), the ball is in the air and on
its way to the target wide receiver (WR). Image 1(c) shows the last moments of
the play, where cornerback (CB) and WR are fighting for the ball and CB is
committing a DPI.

(a) QB throws the ball to the WR.

(b) WR and CB fighting for the ball which is in the air.

(c) Ball arrives and DPI is committed.

Figure 1: Example of play which resulted in DPI

Processing starts with merging plays, games and 17 weeks of tracking data. As
DPI can only occur when a pass is played forward, every play that does not
contain the ”pass_forward” event is discarded. Tracking data contains some
duplicate timestamp values, therefore these had to be cleaned. All records
were grouped according to game id, timestamp and frame id. Iterating through
grouped data, records that had the same timestamp but different frame id were
split by adding 10 ms on the previous timestamp. The minimal difference
between timestamps is 100 ms, so this way, we have ensured that every
timestamp within the play corresponds to the unique moment in the game. Next,
all data which occurred before the ”pass_forward” event is discarded. Every
play starts with the ”pass_forward” (image 1(a)) event and afterwards is a
”None” event (image 1(b)) which indicates that nothing important has happened.
Next event, following these two, can be any: ”tackle”, ”pass_outcome_caught”,
”pass_unsuccessful”, etc. That event, which follows, is interpreted as end-of-
play, and that is the moment in which we choose the most important players
responsible for the DPI. This situation is shown on image 1(c). The assumption
is that, in a majority of cases, opposing players which are closest to the
ball are the ones to watch for a DPI event. That is why Euclidean distance is
calculated between the position of the ball and all the players. From each
team, players having the smallest distance to the ball, in that particular
moment, are picked (along with the ball), and a new data set is created.
Additionally, data were normalised according to the play direction. That way,
all the attacks lead in the same direction – right. Also, it was important to
distinguish the attacker from the defender, so that information was created
from the available information concerning the team in possession. Attacker,
defender and ball information were all merged in a single row, and that
included acceleration, speed, orientation and direction information. Data that
could not be merged easily was a current x and y position on the field. This
was solved by calculating the Euclidean distance between all three parties:
defender and attacker, attacker and the ball, defender and the ball. In
addition to this data, most meaningful events were added as binary static
variables. These events included: ”pass_arrived”, ”pass_outcome_caught”,
”tackle”, ”first_contact”, ”pass_outcome_incomplete” and ”out_of_bounds”. All
processing steps are shown in Fig. 2.

Figure 2: Preprocessing steps

Players whose distance from each other (attacker and defender) is high, are
unlikely to commit a foul as they are not close enough. In order to determine
the threshold value for acceptance of a given play, DPI records were further
examined. By examining the whole dataset, it proved that 90% of DPI classified
plays were below the value of 5.56 for the maximal distance between the
defender and the attacker in a particular play. This threshold was then used
on the whole dataset which resulted in the final distribution where the number
of non-DPI plays was 9,529 (97.68%) and the number of DPI plays was 231
(2.32%). This filter eliminated possible outliers and enabled the focus to be
shifted on the relevant samples. Everything was split into training (56%),
validation (14%) and test (30%) set with distributions shown in Table I.

TABLE I: Data set class distribution. | Training | Validation | Test | %
---|---|---|---|---
non-DPI | 5336 | 1334 | 2859 | 97.6
DPI | 130 | 32 | 69 | 2.4

###  II-C Prediction Models

A sequence of events is important when considering DPI. That is why we opted
for using time-series models for binary classification. The following include:
Long-Short Term Memory (LSTM), Gated Recurrent Unit (GRU), Attention Neural
Network (ANN) and, finally, multivariate LSTM Fully Convolutional Network
(MLSTM-FCN)[3].

LSTM is a recurrent neural network (RNN), commonly used for tasks such as
handwriting recognition, speech recognition and anomaly detection. An LSTM
unit is composed of a cell, an input gate, an output gate and a forget gate.
They are well suited for making predictions based on time series data and are
able to cope with the vanishing gradient problem which can occur when using
regular RNNs [4].

The GRU is somewhat similar to an LSTM unit – it has a forget gate, however,
it contains fewer parameters, and has no output gate. It is used in polyphonic
music modelling, speech signal modelling and natural language processing
(NLP). The GRU was picked because it has been shown to exhibit better
performance on smaller datasets [5].

The attention mechanism in an ANN model focuses on the important parts of the
data and fades out the rest. ANNs are mainly used in NLP and computer vision.
It is an upgrade on the LSTM approach and it was extensively used in
transformer networks [6].

MLSTM-FCN is an approach using a combination of convolutional layers and LSTM
units [3]. It showed very good results on various, even unbalanced datasets.
The authors have also provided their code implementation of MLSTM-FCN
444https://github.com/titu1994/LSTM-FCN (last accessed on 26. May 2021).

LSTM and GRU models were implemented using Keras deep learning API and
Tensorflow 2.0 library. ANN model was constructed using Keras Attention
Mechanism library 555https://github.com/philipperemy/keras-attention-mechanism
(last accessed on 26. May 2021) built on top of an LSTM model. All models
consisted of only one hidden layer, having either 8, 64 or 128 neurons.
Experimental testing proved that increasing the number of layers did not
improve model performance. Furthermore, it significantly increased model
training time, thus in this paper we focus only on models having only one
layer and a variable number of hidden cells.

###  II-D Handling imbalanced data

Dataset for predicting DPI is highly imbalanced which needs to be taken into
consideration when training a model and interpreting the results. This issue
is usually solved by using techniques such as oversampling the minority class,
undersampling the majority class, creating new artificial data using
algorithms such as SMOTE and by manipulating class weights [7]. The process of
undersampling was tested but it did not result in a satisfying performance
outside the training set. Generating new artificial data is difficult,
considering multiple variables changing over time, so this approach was not
considered. Oversampling is very similar to changing class weights so we have
focused on the latter. Several weight factors were tested and, in the end,
class weight formula 1 proved to work the best with class 0 (non-DPI) weights
being 0.51 and class 1 (DPI) being 20.52. It is calculated using the following
expression:

$w_{class}=\frac{n\\_inst}{n\\_classes*n\\_inst_{class}},$ (1)

where $w_{class}$ represents the calculated weight for a given class,
$n\\_inst$ denotes the number of all instances in a dataset, $n\\_classes$
denotes the number of distinct classes, and $n\\_inst_{class}$ denotes the
number of instances of a given class.

##  III Results

Having in mind the imbalanced nature of the problem, classification accuracy
was not considered as an appropriate model evaluation metric. Instead, we used
precision, recall, area under the curve (AUC) and F1 score. From the mentioned
metrics, we marked recall to be the most important one because we want as few
missed DPI classifications as possible.

All 12 model combinations have been trained 5 times each, and from these, only
those exhibiting the best performance on the validation set were picked.
Models tried to reproduce the best precision at recall threshold being 0.8. A
recall is the most important metric as it would be better to predict a false
DPI and then check it manually (using video replay of the action) than to miss
it. Model performance on the test set can be seen in Table II.

TABLE II: Model performance on the test set. Model | Cells | Recall | Precision | F1 | AUC
---|---|---|---|---|---
LSTM | 8 | 0.826 | 0.08 | 0.147 | 0.796
LSTM | 64 | 0.855 | 0.091 | 0.164 | 0.821
LSTM | 128 | 0.884 | 0.0748 | 0.138 | 0.807
ANN | 8 | 0.841 | 0.072 | 0.133 | 0.787
ANN | 64 | 0.884 | 0.073 | 0.135 | 0.803
ANN | 128 | 0.855 | 0.076 | 0.139 | 0.798
GRU | 8 | 0.855 | 0.023 | 0.046 | 0.487
GRU | 64 | 0.87 | 0.074 | 0.137 | 0.801
GRU | 128 | 0.884 | 0.072 | 0.133 | 0.801
LSTM-FCN | 8 | 0.551 | 0.079 | 0.137 | 0.695
LSTM-FCN | 64 | 0.609 | 0.068 | 0.122 | 0.701
LSTM-FCN | 128 | 0.855 | 0.05 | 0.095 | 0.727

Best performing scores are emphasised. Three models achieved the best recall
of 0.884 on the test set. In order to provide additional information about
generalisation quality of models, both validation (V) and test (T) set
performance is presented in Table III. The best model according to all other
metrics (precision, F1 and AUC) was the LSTM model having 64 hidden-layer
neurons. Out of the models exhibiting the highest recall, the best performing
model considering precision is the LSTM model having 128 hidden-layer neurons.
Classification confusion matrix for this model is shown in Fig. 3. Model
performance is discussed in more detail in section IV. In addition to the
presented results, we provide full code for preprocessing, training and
evaluating models that will simplify future research in this area and enable
easier replication of results 666The code is available at
https://github.com/askoki/nfl_dpi_prediction.

TABLE III: Model performance on test (T) versus validation (V) set Model | Recall(T) | Recall(V) | Precision(T) | Precision(V)
---|---|---|---|---
LSTM (64) | 0.855 | 0.844 | 0.091 | 0.085
LSTM (128) | 0.884 | 0.938 | 0.075 | 0.078
ANN (64) | 0.884 | 0.969 | 0.073 | 0.079
GRU (128) | 0.884 | 0.938 | 0.072 | 0.077
Figure 3: Classification confusion matrix for the LSTM (128) model on the test
set.

##  IV Discussion

The models presented in this work fail to solve the problem of detecting
seldom occurring events such as DPI. Changing weight factors, increasing model
complexity or changing the sequence model algorithm all fail to deliver better
results, and an F1 score significantly above 0.15. By looking at the source of
the data – GPS sensors – this comes as no surprise. When players are close to
each other, there is no information from which one can determine if a DPI was
made. Our initial thought was that players’ trajectories might obfuscate the
information concerning a possible DPI, but this was just not enough to detect
this event with high prediction confidence. Initially, all players (on the
pitch) were involved as part of the information from which the models were
trained. This, however, did not give any meaningful results – everything was
classified as non-DPI (the dominant class). We then switched our focus to
include only those players having the highest probability to commit a DPI,
which was described in section II-B. Changes in data processing resulted in
the improvement of model performance but all of them failed to deliver a
recall greater than 0.88 as presented in section III.

An additional challenge when dealing with this problem was the high data
imbalance. Furthermore, there were only 259 possible plays that resulted in a
DPI. This amount of data might not be enough for the ML models to build on
[8]. Gathering DPI plays from more seasons could be beneficial in improving
model efficiency, at least in recall metrics. Improving recall, while keeping
a satisfying precision score, would be a useful automatic preprocessing step
for a follow-up video analysis filter.

Images capture exact events on the pitch, therefore models could learn if a
player made an illegal act or not [9]. On the other hand, tracking data does
not provide any additional information when players are close to each other
and competing for the ball. Analysing sequences of images would provide more
features for a model to work with, which could consequently lead to better
classification performance. Again, the number of DPI data instances would have
to be greater, but this approach does not suffer from a lack of information.
European football (soccer) is using video recordings for a better
understanding of the game [10]. In future work, combining model results from
GPS and video systems might lead to a solution to this highly-complex problem
[11].

##  V Conclusion

The work presented in this paper is the first approach to predict DPI events
in American football using GPS tracking data. DPI is a very rare event
occurring in only 1.46% of all action plays. However, the impact of this
penalty call can be game-changing. By automating this penalty call, the
possibility of one referee call being a game changer would be drastically
decreased. The results show that the prediction of this event, using ML
sequence models, has limited applicability. The models failed to achieve a
recall greater than 0.884 with precision being very low, usually around 0.08.

The data set used for training contained only 259 DPI events. By increasing
the sample size, the recall score could be potentially improved and this
approach could be used as a first step filter for later video sequence
analysis of remaining DPI candidates. On the given dataset, GPS tracking data
alone does not contain enough information in order to classify this complex
event correctly. Future work should take into consideration the amount of DPI
plays which is available and try different approaches, such as video analysis,
in order to try to improve model performance.

## Acknowledgment

This work was supported by the Horizon 2020 project EuroCC 951732 National
Competence Centres in the Framework of EuroHPC, and by the University of
Rijeka, Croatia [grant number uniri-tehnic-18-15 and uniri-tehnic-18-17].

## References

  * [1] P. Wu and B. Gu, “DIRECT: A Two-Level System for Defensive Pass Interference Rooted in Repeatability, Enforceability, Clarity, and Transparency,” p. 12.
  * [2] S. Mittal and S. Tyagi, “Performance Evaluation of Machine Learning Algorithms for Credit Card Fraud Detection,” in _2019 9th International Conference on Cloud Computing, Data Science Engineering (Confluence)_ , Jan. 2019, pp. 320–324.
  * [3] F. Karim, S. Majumdar, H. Darabi, and S. Harford, “Multivariate LSTM-FCNs for Time Series Classification,” _Neural Networks_ , vol. 116, pp. 237–245, Aug. 2019, arXiv: 1801.04503. [Online]. Available: http://arxiv.org/abs/1801.04503
  * [4] S. Siami-Namini, N. Tavakoli, and A. S. Namin, “The Performance of LSTM and BiLSTM in Forecasting Time Series,” in _2019 IEEE International Conference on Big Data (Big Data)_ , Dec. 2019, pp. 3285–3292.
  * [5] S. Yang, X. Yu, and Y. Zhou, “LSTM and GRU Neural Network Performance Comparison Study: Taking Yelp Review Dataset as an Example,” in _2020 International Workshop on Electronic Communication and Artificial Intelligence (IWECAI)_ , Jun. 2020, pp. 98–101.
  * [6] N. Li, S. Liu, Y. Liu, S. Zhao, and M. Liu, “Neural Speech Synthesis with Transformer Network,” _Proceedings of the AAAI Conference on Artificial Intelligence_ , vol. 33, pp. 6706–6713, Jul. 2019. [Online]. Available: https://aaai.org/ojs/index.php/AAAI/article/view/4642
  * [7] E.-A. Mînăstireanu and G. Meșniță, “Methods of Handling Unbalanced Datasets in Credit Card Fraud Detection,” _BRAIN. Broad Research in Artificial Intelligence and Neuroscience_ , vol. 11, no. 1, pp. 131–143, Mar. 2020, number: 1. [Online]. Available: https://www.edusoft.ro/brain/index.php/brain/article/view/994
  * [8] M. Maalouf and T. B. Trafalis, “Rare events and imbalanced datasets: an overview,” _International Journal of Data Mining, Modelling and Management_ , vol. 3, no. 4, p. 375, 2011. [Online]. Available: http://www.inderscience.com/link.php?id=42935
  * [9] R. Chellappa, A. Veeraraghavan, and G. Aggarwal, “Pattern Recognition in Video,” in _Pattern Recognition and Machine Intelligence_ , ser. Lecture Notes in Computer Science, S. K. Pal, S. Bandyopadhyay, and S. Biswas, Eds. Berlin, Heidelberg: Springer, 2005, pp. 11–20.
  * [10] M. Stein, H. Janetzko, A. Lamprecht, T. Breitkreutz, P. Zimmermann, B. Goldlücke, T. Schreck, G. Andrienko, M. Grossniklaus, and D. A. Keim, “Bring It to the Pitch: Combining Video and Movement Data to Enhance Team Sport Analysis,” _IEEE Transactions on Visualization and Computer Graphics_ , vol. 24, no. 1, pp. 13–22, Jan. 2018, conference Name: IEEE Transactions on Visualization and Computer Graphics.
  * [11] “Combining Video and Player Telemetry for Evidence-based Decisions in Soccer:,” in _Proceedings of the International Congress on Sports Science Research and Technology Support_. Vilamoura, Algarve, Portugal: SCITEPRESS - Science and and Technology Publications, 2013, pp. 197–205. [Online]. Available: http://www.scitepress.org/DigitalLibrary/Link.aspx?doi=10.5220/0004676101970205


# Generative Adversarial Neural Cellular Automata

Maximilian Otte Quentin Delfosse Johannes Czech Kristian Kersting

AIML Lab, Technical University Darmstadt
Darmstadt, Germany

<EMAIL_ADDRESS>

###### Abstract

Motivated by the interaction between cells, the recently introduced concept of
Neural Cellular Automata shows promising results in a variety of tasks. So
far, this concept was mostly used to generate images for a single scenario. As
each scenario requires a new model, this type of generation seems
contradictory to the adaptability of cells in nature. To address this
contradiction, we introduce a concept using different initial environments as
input while using a single Neural Cellular Automata to produce several
outputs. Additionally, we introduce GANCA, a novel algorithm that combines
Neural Cellular Automata with Generative Adversarial Networks, allowing for
more generalization through adversarial training.

The experiments show that a single model is capable of learning several images
when presented with different inputs, and that the adversarially trained model
improves drastically on out-of-distribution data compared to a supervised
trained model.

##  1 Introduction

Regeneration of body parts is an example of the fundamental self-organization
of cells. Even though each cell can only interact with its immediate
surroundings, it acts accordingly to its position inside the body. Cells are
able to react and re-organize depending on external stimulation or
environmental changes [8]. These biological phenomena are one of the
motivations for Neural Cellular Automata (NCAs).

Shortly after the paper introducing NCAs by Mordvintsev et al. [10], several
papers were published showcasing the performance of this architecture on
different tasks. Growing and robustly repairing images [10], texture
generation [12], classification [14] or pixel wise segmentation [16], show the
high diversity of applications for Neural Cellular Automata.

In all previous experiments, NCAs are trained to perform well in a single
situation, producing good-looking results, but defying the nature of the
biological motivation for the model. This is why this paper starts of by
illustrating that the NCA is capable of generating different images depending
on the initial image. These generalization capabilities will then be further
tested on unseen initial images through validation data and out-of-
distribution data. Furthermore, we introduce a new type of NCA, the Generative
Adversarial Neural Cellular Automaton (GANCA), combining the adversarial
training of a GAN structure with the generative capabilities of an NCA, to
increase the performance on out-of-distribution data.

##  2 Foundation

A Neural Cellular Automaton, spreads and computes local information while
using the same program for each local part. An example of an NCA generating
images frame by frame can be seen in Figure 1.

Figure 1: Frame by frame output of three different NCAs growing emojis. Each
image shows progress of frames, starting from a blank (as in Mordvintsev et
al. [10]) or edge image (ours) from the training set. The last two emojis were
generated from the same NCA.  Figure 2: Sketch of the implementation of a
single iteration of a simple Neural Cellular Automaton. The world state
contains 4 channels of R.G.B.A. information, while additional channels contain
latent state information. We use a world state depth of 16, resulting in
around 20k parameters for the NCA. Increasing the depth drastically increases
the number of parameters.

Intuitively speaking, an NCA follows the same mandatory restrictions:

  1. (i)

Every cell only sees its local neighborhood.

  2. (ii)

Every cell runs the same program.

To propagate the local information globally, the NCA spreads this information
throughout time. In most cases the world consists of a grid of cells. An
exemplary grid world is shown in Figure 1, where each pixel represents one
cell.

A cell has a state vector containing information of this cell, and can only
observe its local neighborhood by seeing the state vectors of the closest
cells. Using the program, every cell will use this information to update their
state vector. This way, information can be propagated through the whole world.

All NCA architectures inherently follow these statements. Some architectures
add additional constraints, while others only differ in the program that each
cell will execute.

###  2.1 Formalization

Using the restrictions, we propose a new formalization for the NCA
architecture. Assuming a grid world111A grid world is not mandatory. However,
assuming a grid world simplifies the formalization, making it easier to
follow., $S_{t}\in\mathbb{R}^{W\times H\times D}$ defines the world state at
time step $t$, where $W$ is the width, $H$ the height and $D$ the depth of the
world. The depth $D$ also describes the size of the state vectors for each
cell. The state vector of a cell at position $(x,y)\in W\times H$, during time
step $t$ will be written as $\mathbf{c}_{xy}^{t}\in\mathbb{R}^{D}$.

This will lead to a definition of the world state $S_{t}$:

$\displaystyle
S_{t}:=\begin{pmatrix}\mathbf{c}_{0,0}^{t}&\dots&\mathbf{c}_{0,W}^{t}\\\
\vdots&\ddots&\vdots\\\
\mathbf{c}_{H,0}^{t}&\dots&\mathbf{c}_{H,W}^{t}\end{pmatrix}.$

Using these notations, the first statement (i) can be written as:

$\displaystyle\begin{split}N(\mathbf{c}_{x,y}^{t})&:=\begin{pmatrix}\mathbf{c}_{x-1,y-1}^{t}&\mathbf{c}_{x,y-1}^{t}&\mathbf{c}_{x+1,y-1}^{t}\\\
\mathbf{c}_{x-1,y}^{t}&\mathbf{c}_{x,y}^{t}&\mathbf{c}_{x+1,y}^{t}\\\
\mathbf{c}_{x-1,y+1}^{t}&\mathbf{c}_{x,y+1}^{t}&\mathbf{c}_{x+1,y+1}^{t}\end{pmatrix},\\\
\mathbf{c}_{x,y}^{t+1}&:=g(\mathbf{c}_{x,y}^{t},N(\mathbf{c}_{x,y}^{t})),\end{split}$
$\displaystyle(\ref{nca:i})$

where $N$ is a neighborhood function returning only the local information
around a cell, the $3\times 3$ neighborhood in this case. The program, or
local transition function, is denoted here as $g$. This can be used to define
the transition function of the NCA as:

$f_{NCA}(\mathbf{c}_{x,y}^{t}):=g(\mathbf{c}_{x,y}^{t},N(\mathbf{c}_{x,y}^{t})).$

The second statement (ii) can now be defined through the update rule of the
whole world state:

$\displaystyle\begin{split}f_{NCA}(S_{t})&:=\begin{pmatrix}f_{NCA}(\mathbf{c}_{0,0}^{t})&\dots&f_{NCA}(\mathbf{c}_{0,W}^{t})\\\
\vdots&\ddots&\vdots\\\
f_{NCA}(\mathbf{c}_{H,0}^{t})&\dots&f_{NCA}(\mathbf{c}_{H,W}^{t})\end{pmatrix},\\\
S_{t+1}&:=f_{NCA}(S_{t}).\end{split}$ $\displaystyle(\ref{nca:ii})$

Using zero-padding, the values outside the boundaries, e.g.
$\mathbf{c}_{-1,-1}^{t}$, are set to 0. Throughout the matrix, the same
function $f_{NCA}$ is applied to every element, running the same program $g$
across all cells.

Using these definitions, one of the final images in Figure 1 can be written
as:

$\displaystyle S_{60}=\underbrace{[f_{NCA}\circ\dots\circ f_{NCA}]}_{\text{60
times}}(S_{0})\ .$

The initial world state $S_{0}$ is, for example, the blank image with only
modified pixels in the middle of the image. The same $f_{NCA}$ transition will
be applied 60 times to result in $S_{60}$.

###  2.2 Implementation

The NCA can be implemented through existing deep learning structures, as it
simply is a ResNet block [5] with two convolutional layers. The first layer is
the perception layer propagating the information of a cell to the neighboring
cells through $3\times 3$ convolution, while the following layer(s) are
$1\times 1$ convolutions for additional computation. A single iteration is a
single pass through this block, which is visualized in Figure 2.

It is possible to train the NCA in a supervised fashion through a pixel-wise
L2 loss, e.g. comparing the first 4 layers produced by the NCA, representing
the RGBA channels, to the target image. Additionally, in order to keep the
image stable over a longer period of time, Mordvintsev et al. [10] introduced
persistence. The goal of persistence is the same as finding an update rule
such that for every $i\in\mathbb{N}$ the following equation holds

$\mathcal{L}_{2}(S_{t_{n}+i})=\mathcal{L}_{2}(S_{t_{n}})+\epsilon\;,$

where $\mathcal{L}_{2}$ is an exemplary loss function, calculating the loss to
the target image at time step $t_{{n}+i}$, with $\epsilon\approx 0$.

Persistence can be accomplished, for example, by having a chance of using the
output of the final NCA iteration of the previous training step as input for
the first iteration of the next training step. This way, the NCA additionally
has to keep the image stable over a possibly infinite period of time.

An exemplary implementation of an NCA and all the experiments presented in
this paper can be found on GitHub222Link to be announced.

##  3 Related Work

Beginning with a collection of articles about differentiable self-organizing
systems333https://distill.pub/2020/selforg/, Mordvintsev et al. [11] motivate
a new approach to self-organization in systems.

In the first article of this thread, Mordvintsev et al. [10] introduce the
concept of Neural Cellular Automata, where they grew emojis from a blank seed
using a single NCA. The objective was to start from a blank image and start to
grow the emoji step by step. This was further extended by regrowing the image
after it has been damaged by a user interaction.

Their follow-up article uses the NCA for the MNIST classification problem
[14]. This is done by using the information of the state vector from each
cell, such that each cell will classify itself as one of the classes from the
MNIST set. Even though the task is vastly different to the first NCA
application, the training is very similar.

The third paper in the timeline, by Sandler et al. [16], is not part of the
self-organizing thread. In this paper, the task is to use the NCA for pixel-
wise segmentation and classification. With this paper, they introduced several
new ways of training the NCA, which will be partly used throughout the
experiments.

The most recent article by Niklasson et al. [12] focused on creating textures
with NCA architectures. Here, they used the information of a VGG-16 ([17])
network to apply a loss on the generated texture, allowing for the NCA to
generate good-looking textures.

##  4 Methods

This section begins by extending the idea of generating images with an NCA, by
producing multiple target images with a single NCA. Moreover, this training
concept will then be improved in generalization by adversarially training the
NCA, creating the Generative Adversarial Neural Cellular Automata (GANCA).

###  4.1 Multiple target images

Figure 3: Example emojis for training, validation and out-of-distribution
data. “Edge” is the input image with only edge information, while “GT” shows
the ground truth image. Every ground truth image is an emoji from the Windows
10 Segoe UI Emoji font. The out-of-distribution data are hand drawn images,
resembling faces, but vastly different to the training and validation images.
Figure 4: Visualization of the Generative Adversarial Neural Cellular Automata
(GANCA) architecture with a very similar setup compared to a standard GAN
architecture. The generator now uses several iterations of the same NCA to
generate an image. Additionally, the input for the generator is an image,
which is in our task an edge image generated from the real images.

To generate different images based on the input, the input has to contain
information of the target image. Our approach here is to change the dataset
for training to contain a ground truth image as the target and an image
consisting of the edges of the ground truth image, which will be used as the
input.

The edge image is obtained by using an edge detection algorithm, a Canny
filter [2] in this case, on the ground truth image. Examples are shown in
Figure 3.

This way, the NCA has a chance to differentiate between the shape of the input
image to generate different fully colored emojis. Furthermore, the performance
will be tested on a validation set from the same distribution and on an out-
of-distribution dataset.

The out-of-distribution images are hand drawn edges which are not perfectly
round or have the same line width etc. This is used to test how the NCA will
react on images vastly different from the training examples.

###  4.2 Generative Adversarial Training

The generalization performance on out-of-distribution inputs, after training
on multiple target images, can be further improved through partly444As the
real images are used to generate the initial image for the NCA, the task is
not fully unsupervised. This step is not mandatory, and edge images not
directly related could be used as well. unsupervised training. To train
unsupervised, we use adversarial training from GAN architectures [3], where
several NCA steps replace the generator. Because the NCA operates on images,
the input also changes to an image, instead of a random value vector. In our
case, the GAN will be trained on multiple emoji faces, as used in section 4.1.
As the goal of the training is to transform an edge image into a colored
version, other GAN architectures show strong similarities. Because the edge
image is based on a specific emoji, the GAN structure can be considered
conditional [9]. However, the GANCA also shows strong relations to the
Image2Image GAN [6], or Cycle GANs [18] in general.

The Generative Adversarial Neural Cellular Automata (GANCA) architecture
concept is explained in Figure 4. This is very similar to a standard GAN
structure, with the main difference being the generator and its input. The
generator in the GANCA uses an NCA to update the input edge image step by step
with only local information to produce an image. The input edge image is based
on the set of real images provided for the discriminator reduced to edges. The
NCA uses a random amount of iterations in a defined range, e.g. between 50 and
60, to produce the image. A single iteration is a single pass through an NCA
block, as visualized in Figure 2.

As GANs are notoriously difficult to train, several papers have been published
to increase and stabilize the performance ([1], [4], [7], [13], [15]). A good
improvement to training, is to add noise to the input images of the
discriminator and the output of the generator [7], which makes it a lot harder
to overfit for the discriminator. Adding even a small amount of noise leads to
a drastically more stable performance. The second change we included, is to
smooth the labels for training, 0 or 1 to a value similar to 0.1 or 0.9 as
this tends to improve the performance of GAN models [15]. A comparison using
these training improvements can be found in Figure 5.

(a) Simple GANCA without any modifications

(b) Using improved training techniques

Figure 5: Training the GANCA structure with different settings. The first
image shows the loss during training when using a simple GANCA structure,
while the right image shows a loss graph when training with noise and label
smoothing. A good loss for the generator and discriminator should converge
between 0 and 1, similar to the right plot.

Additionally, using the WGAN loss helped to improve stability. The Wasserstein
loss[1] uses a critic network, which does not output probabilities but instead
values between $[0,\infty)$.

##  5 Results

Without any major modifications, the standard NCA is able to fully reproduce
the training images and keep them stable (persistence), after only 10k steps
with a batch size of 16.

Figure 6: Output for training, standard validation and out-of-distribution
data of the NCA after training for 10k steps on 50 different emoji faces.
“Edge” is the edge image used as the input for the NCA, “NCA” is a single
frame of the output of the NCA, while “GT” shows the target ground truth
image.

These results are visualized in Figure 6, where the NCA is trained on 50
different emoji faces with different edge images as input. The NCA is able to
overfit on the training data, producing very good replicates to the ground
truth images. Simple validation images also look good, while more complex
images are missing color information. As the color information is never
provided, this result is to be expected. However, on out-of-distribution data,
the NCA does not perform very well on any image. Many artifacts are
introduced, and some details are removed.

Using the introduced method of the GANCA, the NCA can be trained adversarially
to increase the out-of-distribution performance.

Figure 7: Output of the GANCA and the standard NCA architecture after training
on 50 different emojis. Edge images used as input here are out-of-distribution
validation images. The GANCA shows significant improvement over the standard
NCA training.

As visualized in Figure 7, the performance on out-of-distribution data
increases drastically in comparison to the standard NCA architecture.
Additional images can be found in the appendix in Section A. Most images
contain all the details and do not introduce any artifacts.

##  6 Discussion

The NCA showed very good results on generating different emojis with just a
single NCA structure. Thereby demonstrating that the architecture has enough
capacity to reproduce all training images, to the extent of overfitting. Even
after overfitting, it was still able to produce decent-looking results on
validation images. Because the NCA is only able to use local information, the
model did not fully overfit on the training data, and still performed decently
on the validation images. This shows that the NCA is inherently able to
generalize through the architecture alone.

These generalization capabilities, specifically on out-of-distribution data,
are further improved through unsupervised adversarial training.

In addition, it should be noted that the number of parameters used in the
generator architecture by using an NCA (around 20k parameters) is much smaller
compared to other generators. This is because a lot of information is placed
in the environment and passed through the image step by step. Because of this
step by step information sharing, the NCA will need a longer time to produce
the final output, compared to standard feed forward architectures. However,
Sandler et al. [16] used asynchronous spatial updates for NCAs, allowing the
use of a grid of processors without global synchronization, for a drastic
decrease in computational time.

These experiments show a proof of concept, as training on high-quality images
with big datasets, was not the main concern. This is still possible and highly
encouraged for future projects. It is very promising to see such a drastic
difference in results of the out-of-distribution data between the adversarial
training and the standard supervised training.

##  7 Conclusion

We proposed two novel approaches for training NCAs, namely by training on
multiple target images with a single model and by adversarial training with
the GANCA architecture. We demonstrated that a single NCA is capable of
learning different emojis and is still able to perform well on validation
images without additional color information. Using existing training
improvements from GAN architectures, NCAs can be trained in an adversarial
fashion, which drastically improve performances on out-of-distribution data.

###  7.1 Future Work

As NCAs have only recently been introduced and show great adaptability to a
wide range of tasks, many possible directions are promising. We strongly
encourage further work that takes advantage of the fact that NCAs use an image
as input and operate on the image step by step.

As a use case, NCA could be used for videos, e.g. for segmentation or
generation, as each frame is connected to previous frames, which is inherently
built in the architecture.

At last, working with user interactions is a promising field. By modifying the
current state of the image, it allows for an easy way to interact with the
model, as already showcased by Mordvintsev et al. [10]. This type of
interactive behavior is very intuitive with an NCA architecture, compared to a
deconvolutional architecture in which the image is generated in a single
forward pass. Moreover, extended by adversarial training, reacting to
unpredictable behavior of users, could be a strong use case.

## References

  * Arjovsky et al. [2017] Martin Arjovsky, Soumith Chintala, and Léon Bottou.  Wasserstein Generative Adversarial Networks.  In _International Conference on Machine Learning_ , pages 214–223. PMLR, July 2017.
  * Canny [1986] John Canny.  A computational approach to edge detection.  _IEEE Transactions on pattern analysis and machine intelligence_ , PAMI-8(6):679–698, 1986.
  * Goodfellow et al. [2014] Ian Goodfellow, Jean Pouget-Abadie, Mehdi Mirza, Bing Xu, David Warde-Farley, Sherjil Ozair, Aaron Courville, and Yoshua Bengio.  Generative adversarial nets.  In Z. Ghahramani, M. Welling, C. Cortes, N. Lawrence, and K. Q. Weinberger, editors, _Advances in Neural Information Processing Systems_ , volume 27. Curran Associates, Inc., 2014.
  * Goodfellow [2015] Ian J. Goodfellow.  On distinguishability criteria for estimating generative models.  In _International Conference on Learning Representations_ , 2015.
  * He et al. [2016] Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun.  Deep Residual Learning for Image Recognition.  In _2016 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 770–778, June 2016.  doi: 10.1109/CVPR.2016.90.
  * Isola et al. [2017] Phillip Isola, Jun-Yan Zhu, Tinghui Zhou, and Alexei A. Efros.  Image-to-Image Translation with Conditional Adversarial Networks.  _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , 2017.  doi: 10.1109/CVPR.2017.632.
  * Jenni and Favaro [2019] Simon Jenni and Paolo Favaro.  On Stabilizing Generative Adversarial Training With Noise.  In _2019 IEEE/CVF Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 12137–12145, Long Beach, CA, USA, June 2019. IEEE.  ISBN 978-1-72813-293-8.  doi: 10.1109/CVPR.2019.01242.
  * Karsenti [2008] Eric Karsenti.  Self-organization in cell biology: A brief history.  _Nature Reviews Molecular Cell Biology_ , 9(3):255–262, March 2008.  ISSN 1471-0080.  doi: 10.1038/nrm2357.
  * Mirza and Osindero [2014] Mehdi Mirza and Simon Osindero.  Conditional Generative Adversarial Nets.  _arXiv:1411.1784 [cs, stat]_ , November 2014.
  * Mordvintsev et al. [2020a] Alexander Mordvintsev, Ettore Randazzo, Eyvind Niklasson, and Michael Levin.  Growing Neural Cellular Automata.  _Distill_ , 5(2):e23, February 2020a.  ISSN 2476-0757.  doi: 10.23915/distill.00023.
  * Mordvintsev et al. [2020b] Alexander Mordvintsev, Ettore Randazzo, Eyvind Niklasson, Michael Levin, and Sam Greydanus.  Thread: Differentiable Self-organizing Systems.  _Distill_ , 5(8):e27, August 2020b.  ISSN 2476-0757.  doi: 10.23915/distill.00027.
  * Niklasson et al. [2021] Eyvind Niklasson, Alexander Mordvintsev, Ettore Randazzo, and Michael Levin.  Self-Organising Textures.  _Distill_ , 6(2):e00027.003, February 2021.  ISSN 2476-0757.  doi: 10.23915/distill.00027.003.
  * Radford et al. [2016] Alec Radford, Luke Metz, and Soumith Chintala.  Unsupervised Representation Learning with Deep Convolutional Generative Adversarial Networks.  In _International Conference on Learning Representations_ , November 2016.
  * Randazzo et al. [2020] Ettore Randazzo, Alexander Mordvintsev, Eyvind Niklasson, Michael Levin, and Sam Greydanus.  Self-classifying MNIST Digits.  _Distill_ , 5(8):e00027.002, August 2020.  ISSN 2476-0757.  doi: 10.23915/distill.00027.002.
  * Salimans et al. [2016] Tim Salimans, Ian Goodfellow, Wojciech Zaremba, Vicki Cheung, Alec Radford, Xi Chen, and Xi Chen.  Improved techniques for training GANs.  In D. Lee, M. Sugiyama, U. Luxburg, I. Guyon, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 29. Curran Associates, Inc., 2016.
  * Sandler et al. [2020] Mark Sandler, Andrey Zhmoginov, Liangcheng Luo, Alexander Mordvintsev, Ettore Randazzo, and Blaise Agúera y Arcas.  Image segmentation via Cellular Automata.  _arXiv:2008.04965 [cs]_ , August 2020.
  * Simonyan and Zisserman [2015] Karen Simonyan and Andrew Zisserman.  Very deep convolutional networks for large-scale image recognition.  In Yoshua Bengio and Yann LeCun, editors, _3rd International Conference on Learning Representations, ICLR 2015, San Diego, CA, USA, May 7-9, 2015, Conference Track Proceedings_ , 2015.  URL http://arxiv.org/abs/1409.1556.
  * Zhu et al. [2017] Jun-Yan Zhu, Taesung Park, Phillip Isola, and Alexei A Efros.  Unpaired image-to-image translation using cycle-consistent adversarial networks.  In _Computer Vision (ICCV), 2017 IEEE International Conference on_ , 2017.

##  Appendix A Additional Images

As including videos in pdfs is not possible, Figure 8 shows the output of
every frame for 36 frames. It should be noted here that after around frame 24
the NCA has finished creating the emoji and will keep the image stable for the
following frames. Additional frames could be added, but they do not show any
or only minor changes.

The following Figure 9 shows the output of the NCA on a different dataset. The
training images look very close to the ground truth images, as the NCA was
able to overfit on the training data. On the validation set, the performance
decreases drastically. For example, the first image shows a tree, which the
NCA mistakenly drew yellow instead of green. Because the NCA does not know the
color of a tree, as no trees are present in the training set, this behavior is
to be expected. Interestingly, the overall shape of each image stays
consistent and only wrong colors are chosen. This behavior is consistent to
the training task of the NCA, as it needs to color some object in some
specific way and keep it stable.

Figure 8: Output of an NCA frame by frame for a single emoji, showing 36
frames. Figure 9: Output of the NCA after training on 50 different emojis from
the “nature” category. The input (Edge) produces the output of the NCA (NCA)
and is compared to the ground truth (GT).

Additional outputs for training, validation and out-of-distribution images are
provided in Figure 10, 11 and 12. In each figure, the first column of images
shows the input edge image, the GANCA output, the output of the NCA and the
ground truth, if it exists. Similar to the example on “nature” images, the
validation results for the supervised trained NCA are missing important color
information, following the same reasoning. Furthermore, the performance of the
GANCA on the training and validation images can not directly be compared to
the standard supervised NCA architecture. This is because through the
unsupervised training, the GANCA was never trained to replicate the ground
truth images.

Figure 10: Additional outputs for the training dataset.

##  Appendix B Additional Training Details

The additional graph in Figure 13 shows the L2 loss when training an NCA
supervised on 50 different emojis. After around 1k steps with a batch size of
16, the NCA stops improving the validation loss. At this point, most images
consist of a yellow mush, resulting in a decent average loss. The training
loss keeps improving for the next steps, while the validation loss keeps
mostly stable.

In Figure 5, the training losses of two different GANCA architectures is
compared. The improved GANCA uses the techniques introduced in Section 4.2.

Figure 11: Additional outputs for the validation dataset Figure 12: Additional
outputs for the out-of-distribution dataset. Figure 13: Training graph of the
standard NCA learning to grow 50 different emoji faces. The loss used is the
L2 loss.