# An Algebraic Approach to Learning and Grounding

Johanna Björklund<EMAIL_ADDRESS>
This work was partially supported by the Swedish Research Council and the
Wallenberg Autonomous Systems, AI, and Software Program Adam Dahlgren
Lindström<EMAIL_ADDRESS>
Frank Drewes<EMAIL_ADDRESS>
Dept. Computing Science Authors are given in alphabetical order Umeå
University

###### Abstract

We consider the problem of learning the semantics of composite algebraic
expressions from examples. The outcome is a versatile framework for studying
learning tasks that can be put into the following abstract form: The input is
a partial algebra ${\mathcal{A}}$ and a finite set of examples
$(\varphi_{1},O_{1}),(\varphi_{2},O_{2}),\ldots$, each consisting of an
algebraic term $\varphi_{i}$ and a set of objects $O_{i}$. The objective is to
simultaneously fill in the missing algebraic operations in ${\mathcal{A}}$ and
ground the variables of every $\varphi_{i}$ in $O_{i}$, so that the combined
value of the terms is optimised. We demonstrate the applicability of this
framework through case studies in grammatical inference, picture-language
learning, and the grounding of logic scene descriptions.

††terms: [††terms: [††terms: [††terms: [

##  1 Introduction

Modern natural language processing literature, and deep learning-based methods
in particular, is critiqued for using terms like learning, grounding, meaning,
and understanding loosely without clear definitions (Bender and Koller, 2020).
Large language models do not learn representations that are sufficient for the
applications they are used for, resulting in, e.g., perpetuation of
discriminatory bias (Bender et al., 2021). Successful representational systems
are usually modular, in that they describe complex concepts by combining
representations for simpler ones. Examples include first-order predicate
logic, where predicates, variables, and connectives are assembled into logic
expressions, or natural language (NL), where lexical and grammatical
constructs are the building blocks of sentences, which in turn combine to
paragraphs, and so on. When learning the components of a representational
system from real-world observations, we seldom observe instances of a concept
in isolation. Even in picture books for children, an image that is intended to
convey the notion of a shape may also be understood to stand for, e.g., a
colour or a size, so the child may need several observations to grasp the
concept. We are therefore interested in exploring the conditions under which
composite semantics can be learnt by example.

To this end, we introduce the notion of a _template algebra_. This is an
algebra ${\mathcal{A}}$ that is defined with respect to a set of typed
operator symbols $\Sigma$. The algebra is non-standard in that (i) there is a
dedicated _evaluation type_ $\tau$ whose domain in ${\mathcal{A}}$ is a
linearly ordered set, and (ii) a subset of the operators for the symbols in
$\Sigma$ have been left undefined. Given a set of terms over $\Sigma$ of type
$\tau$, the learning task is to choose the missing operators (from families of
candidate ones) so that the combined value of the terms is optimal.

To integrate domains that are not finitely generated, the terms may contain
variables which are assigned values from a target domain during evaluation.
With this addition, a learning example is a pair $(\varphi,O)$, where
$\varphi$ is a $\Sigma$-term with variables, and $O$ is a set of suitable
typed elements that can be substituted for the variables. Again, the goal is
to find an optimal solution over the entire set of examples, but the task has
become more complicated, as the learning algorithm must simultaneously decide
what object to map to what variable, and what operators to choose for those
missing. Coming back to the picture book example, this correspond to
simultaneously inferring what ‘red’ means in a phrase like “Look at the red
ball” and what object in the picture constitutes the red ball.

This second subtask, which can be described as linking abstract
representations to target domains, is known as _grounding_. Other examples of
grounding are connecting symbols on a map to features of the terrain, and to
link words in a natural-language search query to tables, columns, and
threshold values in a database. Also when training is done and the algebra
complete, grounding can still remain challenging for unseen examples. However,
it is likely that the more accurately the system has learnt the target
operations, the better it is positioned also to solve the remaining problem of
grounding, because it can more efficiently limit the search space when mapping
objects to variables.

The purpose of our framework is to provide flexible means for setting up
formally defined symbolic, neural, or neural-symbolic tasks for learning from
examples (where the emphasis is on tasks involving neural components).
Moreover, this is done in such a way that corpora – sets of examples of the
type defined by the task – can be generated automatically using grammars and
automata. In summary, our approach provides a unified way to

  * •

formalize learning tasks that involve mixtures of symbolic and neural
components,

  * •

study the problem of grounding as an integral part of other learning tasks,
and

  * •

automatically generate sets of examples for studying proposed learning
algorithms.

To demonstrate the framework’s ability to support a variety of classical and
modern learning approaches, we discuss instantiations of the framework in
three learning scenarios. The first is the grammatical inference of regular
string language from characteristic sets. The second considers picture-
language learning and involves the estimation of affine transformations with
neural networks. The final instantiation serves to ground the variables of a
logic scene description in geometric objects, by training neural networks to
recognise atomic properties of the objects such as colour, shape, and size.
This ability to integrate finite and infinite-state methods makes the proposed
framework a contribution to the field of neuro-symbolic reasoning.

###  1.1 Related work

Learning and grounding is addressed in symbolic, neural, and neuro-symbolic
settings throughout the literature. Our framework provides a way to
systematically study the different methods and how they approach the grounding
problem. In this section we outline important work in the respective fields.

Visual grounding has been addressed in neuro-symbolic machine learning in
various ways. Inductive Logic Programming (ILP, Muggleton and De Raedt (1994))
is a form of symbolic learning and reasoning with first-order clauses for
learning relations in data. Background knowledge is used together with
examples to induce a hypothesis, in the form of a logic program, describing
positive and negative examples in given data. ILP is applied to, e.g.,
scientific discovery, robotics, program analysis (Cropper et al., 2022), with
neuro-symbolic approaches to machine vision problems (Dai et al., 2015;
Varghese et al., 2021).

Probabilistic logic programming (PLP Dantsin (1992); Ng and Subrahmanian
(1992)), provides reasoning under uncertainty, with methods such as De Raedt
et al. (2007). Raedt and Kersting (2008) provides an overview of the
combination of PLP and ILP, Probabilistic ILP. Neuro-symbolic PLP, such as
DeepProbLog, introduces predicates that are realised by neural networks to be
trained, as a way to ground and reason about visual concepts (Manhaeve et al.,
2018; Weber et al., 2019; Winters et al., 2021). In the Neuro-Symbolic Concept
Learner by Mao et al. (2019), programs are taught to perform visual question
answering by combining a neural perception module, a semantic parsing module
to construct programs from language, and a program executor which bridges
these components to provide answers. The idea of Neural State Machines by
Hudson and Manning (2019) builds on probabilistic graphs to learn and reason
about concepts for visual question answering. Logic Tensor Networks (Serafini
and Garcez, 2016; Badreddine et al., 2022) have been used for semantic image
interpretation as a partial grounding problem (Donadello et al., 2017). Garcez
et al. (2019) gives an overview of how learning and reasoning can be
integrated, and how logical representations are used for that purpose.

Answer Set Programming (ASP) is another approach to knowledge representation
and reasoning based on searching for stable models, answer sets, as solutions
to given logic programs (Niemelä, 1999; Marek and Truszczyński, 1999;
Lifschitz, 2002). ASP is used in decision support systems, planning robotics,
and many other domains (Erdem et al., 2016), with neuro-symbolic examples in
reasoning about objects in video (Suchan et al., 2018).

Finally, grounding in language and vision with neural networks is extensively
researched for tasks such as Visual Question Answering (VQA) (Antol et al.,
2015; Fukui et al., 2016; Chaplot et al., 2018). Neuro-symbolic approaches to
VQA include (Yi et al., 2018).

The above domains all have different perspectives on learning and grounding,
and there are overlaps, such as between ILP and PLP. We can formalise the
described methods and the problems they try to solve, to examine the
similarities, challenges, and opportunities.

###  1.2 Outline

The paper is outlined as follows: Section 1.1 reports on related work on
algebraic approaches and neuro-symbolic learning. Section 2 recalls
fundamental concepts and results, and Section 3 gives introduces the algebraic
framework. Section 4 discusses the framework’s application to learning and
grounding of regular string languages, picture languages, and logic scene
descriptions. Section 5 provides a summary and directions for future work.

##  2 Preliminaries

We begin by recalling some useful definitions and notations from literature.

###  2.1 Sets, numbers, and relations

The set of natural numbers (including $0$) is denoted by ${\rm Nature}$, and
for $n\in{\rm Nature}$, we write $[n]$ as shorthand for $\\{1,\dots,n\\}$. In
particular, $[0]=\emptyset$. For a set $S$, we denote by $2^{S}$ the powerset
of $S$. The domain of a partial function $\delta$ is denoted by
$\mathrm{dom}(\delta)$.

Let $\sim$ be an equivalence relation on a superset of $S$. The _equivalence
class_ of $s$ in $S$ with respect to $\sim$ is the set
$[s]^{S}_{\sim}=\\{s^{\prime}\in S\mid s\sim s^{\prime}\\}$. If $S$ is clear
from the context, we may simply write $[s]^{S}_{\sim}$ as $[s]_{\sim}$. It
should be clear that $[s]_{\sim}$ and $[s^{\prime}]_{\sim}$ are equal if
$s\sim s^{\prime}$, and disjoint otherwise, so $\sim$ induces a partition
$(S/{\sim})=\\{[s]_{\sim}\mid s\in S\\}$ of $S$. We denote by
$\sim_{S}^{\star}$ the transitive, reflexive, and symmetric closure of
${\sim}\cap(S\times S)$. In fact, we shall also use this notation if $\sim$ is
an equivalence relation on a _subset_ of $S$. In this case,
${\sim_{S}^{\star}}={\approx_{S}^{\star}}$, where
${\approx}={\sim}\cup\\{(w,w)\mid w\in S\\}$.

###  2.2 Strings, Languages, and Automata

An alphabet is a finite nonempty set. Given an alphabet $\Xi$ we write
$\Xi^{*}$ for the set of all strings over $\Xi$, and $\varepsilon$ for the
empty string. The lexicographic order on $\Xi^{*}$ is denoted by
$<_{\mathrm{lex}}$. A string language is a subset of $\Xi^{*}$. Let
$u,w\in\Xi^{*}$. The string $u$ is a _prefix_ of $w$ if there is a string
$v\in\Xi^{*}$ such that $uv=w$. We denote the set of all prefixes of $w$ by
$\mathit{prefixes}(w)$. Similarly for a set of strings $S\subseteq\Xi^{*}$,
$\mathit{prefixes}(S)=\cup_{w\in S}\mathit{prefixes}(w)$.

We denote a (partial) _deterministic finite-state automaton_ (DFA) is a tuple
$M=(Q,\Xi,\delta,q_{0},F)$, where $Q$ is a finite set of _states_ , $\Xi$ is
an alphabet of _input symbols_ , the _transition function_ $\delta$ is a
partial function $\delta\colon Q\times\Xi\to Q$, $q_{0}\in Q$ is an _initial
state_ , and $F\subseteq Q$ is a set of _final states_. As usual, we denote by
$\delta_{M}$ the partial function $\delta_{M}\colon\Xi^{*}\to Q$ such that
$\delta_{M}(\varepsilon)=q_{0}$ and $\delta_{M}(wa)=\delta(\delta_{M}(w),a)$
for all $w\in\Xi^{*}$ and $a\in\Xi$ such that the right-hand side
$\delta(\delta_{M}(w),a)$ is defined. The language $L(M)$ _recognised_ by $M$
is defined in the standard way: $L(M)=\\{w\in\Xi^{*}\mid\text{$\delta_{M}(w)$
is defined and in $F$}\\}$. A string language is _regular_ if and only if it
is recognised by some DFA. A DFA $N=(Q^{\prime},\Xi,\delta^{\prime},q_{0},F)$
is a _subautomaton_ of $M$ if $Q^{\prime}\subseteq Q$ and
$\delta^{\prime}\subseteq\delta$ (if $\delta$ is viewed as a subset of
$Q\times\Xi\times Q$).

Let $L\subseteq\Xi^{*}$ be a string language and $w\in\Xi^{*}$. To simplify
notation, may use $L$ as a predicate and write $L(w)$ to denote the statement
$w\in L$. The _Nerode congruence_ $\sim_{L}$ with respect to $L$ is the binary
relation on $\Xi^{*}$ defined by $u\sim_{L}v$ if and only if $L(uw)=L(vw)$ for
all $w\in\Xi^{*}$. It is well-known that $\sim_{L}$ is an equivalence
relation, and as such partitions $\Xi^{*}$ into a set of congruence classes
$(\Xi^{*}/{\sim_{L}})$. We recall from the Nerode theorem that
$\left|(\Xi^{*}/{\sim_{L}})\right|$ is finite if and only if $L$ is regular. A
string $u\in\Xi^{*}$ is _live_ (with respect to $L$ if $u=\varepsilon$ or
$uw\in L$ for some $w\in\Xi^{*}$. A congruence class in $(\Xi^{*}/{\sim_{L}})$
is live if it contains a live string. If $L$ is regular, the canonical DFA
recognizing $L$ is $M_{L}=(Q,\Xi,\delta,q_{0},F)$ where
$Q=\\{B\in(\Xi^{*}/{\sim_{L}})\mid\text{$B$ is live}\\}$ and
$q_{0}=[\varepsilon]_{\sim_{L}}$. (Note that we consider the partial canonical
DFA $M_{L}$ that contains only the live congruence classes as states.)

###  2.3 Terms and Algebras

For a set $\Gamma$ of types, a _$\Gamma$ -typed alphabet_ or simply _typed
alphabet_ is a pair $(\Sigma,\mathit{type}_{\Sigma})$ such that $\Sigma$ is a
finite set of symbols and $\mathit{type}_{\Sigma}\colon\Sigma\to\Gamma^{+}$
assigns to every $\sigma\in\Sigma$ a type signature
$\mathit{type}_{\Sigma}(\sigma)\in\Gamma^{+}$. If
$\mathit{type}_{\Sigma}(\sigma)=\gamma_{1}\cdots\gamma_{k}\gamma$, we usually
indicate this by writing $\sigma\colon\gamma_{1}\cdots\gamma_{k}\to\gamma$,
leaving $\mathit{type}_{\Sigma}$ implicit. If $k=0$, we furthermore abbreviate
$\sigma\colon\gamma_{1}\cdots\gamma_{k}\to\gamma$ by $\sigma\colon\gamma$, and
if all symbols $\sigma\in\Sigma$ satisfy
$\left|\mathit{type}_{\Sigma}(\sigma)\right|=1$, then we call $\Sigma$ a _leaf
alphabet_.

Let $\Sigma$ be a $\Gamma$-typed alphabet. The family
$(\gamma)_{\gamma\in\Gamma}$ of sets $\gamma$, called _terms of type $\gamma$
over $\Sigma$_, is defined by simultaneous induction: $\gamma$ is the smallest
set of formal expressions $f[t_{1},\dots,t_{k}]$ such that
$f[t_{1},\dots,t_{k}]\in\gamma$ for all
$f\colon\gamma_{1}\cdots\gamma_{k}\to\gamma$ in $\Sigma$ and
$t_{1}\in{\gamma_{1}},\dots,t_{k}\in{\gamma_{k}}$.111We assume that the meta-
symbols ‘$[$’, ‘$]$’, and the comma are not in $\Sigma$.

Regular tree grammars are a well-known formalism for generating sets of terms.
To recall them briefly here, such a grammar is a tuple $g=(\Sigma,N,R,S)$
where $\Sigma$ and $N$ are disjoint $\gamma$-typed alphabets for some set
$\Gamma$ of types, where $N$ is a leaf alphabet, $R$ is a finite set of rules
of the form $A\to t$ where $A\colon\gamma$ is in $N$ and $t\in\gamma$ for some
$\gamma\in\Gamma$, and $S\in N$. Derivations according to $g$ start with $S$
and replace, in each step, an occurrence of a leaf $A\in N$ in the current
term $s$ by a term $t$ such that $(A\to t)\in R$. If $s^{\prime}$ is the
resulting term, this is written $s\to_{g}s^{\prime}$. The language $L(g)$
generated by $g$ is the set of all term $s\in\gamma$ such that
$S\to_{g}^{*}s$, where $\to_{g}^{*}$ denotes the transitive reflexive closure
of $\to_{g}$. Note that $L(g)\subseteq\gamma$, where $\gamma$ is the type of
$S$, in other words, $S\colon\gamma$.

Let $\Sigma$ be a $\Gamma$-typed alphabet. A $\Sigma$-algebra ${\mathcal{A}}$
is a pair
$(({\mathbb{A}}_{\gamma})_{\gamma\in\Gamma},(f_{\mathcal{A}})_{f\in\Sigma})$
where ${\mathbb{A}}_{\gamma}$ is a set for all $\gamma\in\Gamma$ and
$f_{\mathcal{A}}$ is a function that maps
${\mathbb{A}}_{\gamma_{1}}\times\cdots\times{\mathbb{A}}_{\gamma_{k}}$ to
${\mathbb{A}}_{\gamma}$ for every $f\colon\gamma_{1}\cdots\gamma_{k}\to\gamma$
in $\Sigma$. A term $t\in\gamma$ can now recursively be evaluated with respect
to ${\mathcal{A}}$ as usual: if $t=f[t_{1},\dots,t_{k}]$ then
$\mathrm{val}_{\mathcal{A}}(t)=f_{\mathcal{A}}(\mathrm{val}_{\mathcal{A}}(t_{1}),\dots,\mathrm{val}_{\mathcal{A}}(t_{k}))$.
Thus, $\mathrm{val}_{\mathcal{A}}(t)\in{\mathbb{A}}_{\gamma}$.

We extend the evaluation of terms to terms with variables in a standard
manner. For this, let $X_{\ell}$ (where $\ell\in{\rm Nature}$) be a
$\Gamma$-typed leaf alphabet of symbols $x_{1},\dots,x_{\ell}$ called
variables, where $X_{\ell}$ is disjoint with $\Sigma$. Now, consider a term
$t\in X_{\ell}]^{\gamma}$, where $\mathit{type}_{X_{\ell}}(x_{i})=\gamma_{i}$
for all $i\in[\ell]$. Then $\mathrm{val}_{\mathcal{A}}^{X_{\ell}}(t)$ is the
function
$\varphi\colon{\mathbb{A}}_{\gamma_{1}}\times\cdots\times{\mathbb{A}}_{\gamma_{\ell}}\to{\mathbb{A}}_{\gamma}$
defined recursively as follows, for all
$a_{1}\in{\mathbb{A}}_{\gamma_{1}},\dots,a_{\ell}\in{\mathbb{A}}_{\gamma_{\ell}}$:

  1. 1.

If $t=x_{i}$ for some $i\in[\ell]$, then
$\varphi(a_{1},\dots,a_{\ell})=a_{i}$.

  2. 2.

If $t=f[t_{1},\dots,t_{k}]$, then
$\varphi(a_{1},\dots,a_{\ell})=f(\mathrm{val}_{\mathcal{A}}^{X_{\ell}}(t_{1})(a_{1},\dots,a_{\ell}),\dots,\mathrm{val}_{\mathcal{A}}^{X_{\ell}}(t_{k})(a_{1},\dots,a_{\ell})$.

Note that this definition is consistent with the evaluation of terms without
variables when $\ell=0$, i.e.,
$\mathrm{val}_{\mathcal{A}}(t)=\mathrm{val}_{\mathcal{A}}^{\emptyset}(t)$ for
terms $t\in\gamma=\emptyset]^{\gamma}$. In the following, we will simply write
$\mathrm{val}_{\mathcal{A}}$ instead of
$\mathrm{val}_{\mathcal{A}}^{X_{\ell}}$ since $X$ will be understood from the
context (or be sufficiently generic to be of lesser interest). In the
following, we shall further generally assume that $X_{\ell}$ denotes an
appropriate alphabet of $\Gamma$-typed variables, if $\Gamma$ is understood
from the context.

##  3 Learning from Algebraic Expressions

We now formalise an algebraic framework for learning and grounding. Let
$\Sigma$ be a $\gamma$-typed alphabet. A _template $\Sigma$-algebra (over
$\Gamma$)_ is defined just like a $\Sigma$-algebra over $\Gamma$, with the
exception that $f_{\mathcal{A}}$ is undefined for some of the symbols
$f\in\Sigma$. These $f\in\Sigma$ represent the functions to be learned. An
_instance_ of ${\mathcal{A}}^{\prime}$ is a $\Sigma$-algebra such that
$f_{{\mathcal{A}}^{\prime}}=f_{\mathcal{A}}$ for all $f\in\Sigma$ for which
$f_{\mathcal{A}}$ is defined.

Consider a template $\Sigma$-algebra as above, and assume that a type
$\tau\in\Gamma$ is designated as the _evaluation type_ , for which an
additional linear order $\leq$ on ${\mathbb{A}}_{\tau}$ is specified, as well
as a summation operation $\bigoplus$ that is well-defined on every finite
subset of ${\mathbb{A}}_{\tau}$. Thus, every finite subset of
${\mathbb{A}}_{\tau}$ has uniquely defined maxima and minima. An _example_ is
a pair $(\varphi,O)$ consisting of a term $\varphi\in X_{\ell}]^{\tau}$ and a
set $O\subseteq\bigcup_{\gamma\in\Gamma}{\mathbb{A}}_{\gamma}$. Suppose that
$\mathit{type}_{X_{\ell}}(x_{i})=\gamma_{i}$. Then the set $[O\to X_{\ell}]$
of all _groundings of $O$_ is the set of all injective mappings $g\colon
X_{\ell}\to O$ such that $g(x_{i})\in{\mathbb{A}}_{\gamma_{i}}$ for all
$i\in[\ell]$. Given an instance ${\mathcal{A}}^{\prime}$ of ${\mathcal{A}}$,
the _value_ of an example $S=(\varphi,O)$ is

$\mathrm{val}_{{\mathcal{A}}^{\prime}}(S)=\operatorname{opt}_{g\in[O\to
X_{l}]}\mathrm{val}_{{\mathcal{A}}^{\prime}}(\varphi)(g(x_{1}),\dots,g(x_{\ell}))\enspace,$
(1)

where $\operatorname{opt}\in\\{\min,\max\\}$ is a specified optimisation
criterion.

Given a finite set $\mathcal{S}$ of examples, the learning goal is to find an
instance ${\mathcal{A}}^{\prime}$ of ${\mathcal{A}}$ that optimises the total
value

$\bigoplus_{S\in\mathcal{S}}\mathrm{val}_{{\mathcal{A}}^{\prime}}(S)$ (2)

of all examples. Since the desired outcome ${\mathcal{A}}^{\prime}$ depend on
which algebras ${\mathcal{A}}^{\prime}$ are admissible solutions, these must
be made explicit when formalising the learning task. In particular, for every
$f\colon\gamma_{1}\cdots\gamma_{k}\to\gamma$ in $\Sigma$ such that
$f_{{\mathcal{A}}}$ is undefined, we specify a set $\mathcal{F}_{f}$ of
candidate functions
$g\colon{\mathbb{A}}_{\gamma_{1}}\times\cdots\times{\mathbb{A}}_{\gamma_{k}}\to{\mathbb{A}}_{\gamma}$
for $f_{{\mathcal{A}}^{\prime}}$.

##  4 Example Instantiations of the Framework

To illustrate how the algebraic framework of Section 3 can be instantiated to
capture various scenarios for algorithmic learning, we now describe three
application domains.

###  4.1 Regular languages

The first instance we consider is the grammatical inference of regular
languages from finite data. If the data constitutes a _characteristic set_ (de
la Higuera, 1997), then a finite automaton for the target language can be
computed in polynomial time in the size of that set (Oncina and Garcia, 1992).
Intuitively, a characteristic set contains strings that represent every state
and every transition of the unique minimal DFA for the target language. We
discuss a similar setting using our framework, in order to illustrate how
traditional automata learning fits into it.

Throughout the remainder of this subsection, let $\Xi$ be a finite, totally
ordered, set of symbols, and $L\subseteq\Xi^{*}$ be a fixed but arbitrary
regular language. Let the set of types be $\Gamma=\\{\alpha,\beta\\}$, the
$\Gamma$-typed alphabet be
$\Sigma=\\{\mathit{accept}\colon\alpha\to\beta,\,\mathit{equiv}\colon\alpha\times\alpha\to\beta,\,\neg\colon\beta\to\beta\\}$,
and the algebra be
${\mathcal{A}}=(({\mathbb{A}}_{\gamma})_{\gamma\in\Gamma},(f_{\mathcal{A}})_{f\in\Sigma})$,
where ${\mathbb{A}}_{\alpha}=\Xi^{*}$ and
${\mathbb{A}}_{\beta}=\\{\mathrm{false},\mathrm{true}\\}$. The operation
$\neg_{\mathcal{A}}$ is logic negation. The operations
$\mathit{accept}_{\mathcal{A}}$ and $\mathit{equiv}_{\mathcal{A}}$ are both
undefined: The characteristic function
$\mathit{accept}_{\mathcal{A}}\colon\Xi^{*}\to\\{\mathrm{false},\mathrm{true}\\}$
for the language $L$ is our learning target, and
$\mathit{equiv}_{\mathcal{A}}$ will be instantiated to model the Nerode
congruence $\sim_{L}$ of $L$. Thus, admissible instantiations are algebras
${\mathcal{A}}_{L}$ in which $\mathit{accept}_{{\mathcal{A}}^{\prime}}$ is the
characteristic function of a regular language $L$ and
$\mathit{equiv}_{{\mathcal{A}}^{\prime}}$ the Nerode congruence of $L$.

Note that, in this instance of our framework, an example is a pair
$(\varphi,O)$ where $\varphi$ can be assumed to be taken from
$\\{\mathit{accept}[x],\neg[\mathit{accept}[x]],\mathit{equiv}[x,y],\neg[\mathit{equiv}[x,y]]\\}$
for variables $x,y$ and a set $O$ of strings. For the two positive terms
$\mathit{accept}[x]$ and $\mathit{equiv}[x,y]$, we furthermore restrict
ourselves to examples such that the number of strings in $O$ is equal to the
number of variables in $\varphi$, i.e., one or two. We let
$\textrm{false}<\textrm{true}$. In Equation (1), we let
$\operatorname{opt}=\min$. (Note that this choice is important only for the
examples using negation, because the positive examples have as many objects as
variables, and $\mathit{equiv}_{{\mathcal{A}}^{\prime}}$ is required to be
symmetric.) Finally, for Equation (2), we take $\bigoplus$ to be $\bigwedge$,
that is, logic conjunction. Thus, the optimisation goal is to find a
congruence relation that respects the partial information provided through the
set of examples.

The mapping $\mathit{pred}\colon(\Xi^{*}/{\sim_{L}})\to
2^{(\Xi^{*}/{\sim_{L}})\times\Xi}$ is defined as
$\mathit{pred}(B)=\\{(D,\xi)\mid D\xi\subseteq B\\}$ for every
$B\in(\Xi^{*}/{\sim_{L}})$. Thus, intuitively, in the minimal DFA for $L$, in
which the live congruence classes of $\sim_{L}$ are the states,
$\mathit{pred}(B)$ is the set of pairs of predecessor states of $B$, together
with the transition symbols that take these to $B$. The congruence class $B$
is a _convergence_ if
$|B\cap\\{\varepsilon\\}|+\left|\mathit{pred}(B)\right|>1$. Let $\mathcal{S}$
be a set of examples and denote by $\mathit{str}(\mathcal{S})$ the set of all
strings that occur in examples of the forms $(\mathit{accept}[x],\\{w\\})$ and
$(\mathit{equiv}[x,y],\\{u,w\\})$. The set $\mathcal{S}$ is _sufficient_ for
$L$ if:

  1. 1.

$\mathcal{S}$ is _faithful_ (with respect to $L$), meaning that, for every
example $(\varphi,O)\in\mathcal{S}$, the set $O$ contains only live strings
and there is a grounding $g\in[O\to X_{l}]$ such that
$\mathrm{val}_{{\mathcal{A}}_{L}}(g(x_{1}),\dots,g(x_{\ell}))=\mathrm{true}$
(where $\ell$ is such that $\varphi\in X_{\ell}]^{\beta}$).

  2. 2.

For every live $B\in(\Xi^{*}/{\sim_{L}})$,

    1. (a)

If $B\subseteq L$, then $(\mathit{accept}[x],\\{w\\})\in\mathcal{S}$ for some
$w\in B$.

    2. (b)

If $B$ is a convergence, then for every $(D,\xi)\in\mathit{pred}(B)$,

$D\xi\cap\mathit{str}(\mathcal{S})\,=\,D\xi\cap\mathit{prefixes}(\mathit{str}(\mathcal{S}))\,\not=\,\emptyset\enspace.$

  3. 3.

For every $w\in\mathit{str}(\mathcal{S})$ that is not minimal (with respect to
$<_{\mathrm{lex}}$) in $[w]^{\mathit{str}(\mathcal{S})}_{\sim_{L}}$ there is a
$u$ in $[w]^{\mathit{str}(\mathcal{S})}_{\sim_{L}}$ such that
$u<_{\mathrm{lex}}w$ and $(\mathit{equiv}[x,y],\\{u,w\\})\in\mathcal{S}$.

  4. 4.

For every pair $B,B^{\prime}\in(\Xi^{*}/{\sim_{L}})$ of live congruence
classes, $B\neq B^{\prime}$ if and only if $\mathcal{S}$ contains an example
$(\neg\mathit{equiv}[x,y],O)$ such that $|O\cap B|=1=|O\cap B^{\prime}|$.

For the regular language $L=(ab)^{*}$, the set of examples in Figure 1 is
sufficient and thus, as we shall see below, allows us to infer $L$. Note,
however, that $L$ is not the only regular language which solves the
optimisation problem given by (2). Another one would, for instance, be the
language $(a^{+}b)^{*}$ obtained from the DFA in Figure 1 by adding a
transition which is not required by the examples but not forbidden either.

$\begin{array}[]{c@{\;}l@{}c}\\{&(\mathit{accept}[x],\,\\{ab\\}),\;(\neg\mathit{equiv}[x,y],\,\\{ababa,aba,b\\})\\\
&(\mathit{equiv}[x,y],\,\\{ab,\varepsilon\\}),\;(\mathit{equiv}[x,y],\\{abab,ab\\}),\\\
&(\mathit{equiv}[x,y],\,\\{ababa,\,aba\\},\;(\neg\mathit{accept}[x],\\{abba\\})&\\}\\\
\end{array}$

$[\varepsilon]_{\sim}$$[aba]_{\sim}$$a$$b$

Figure 1: A sufficient set of examples $\mathcal{S}$ to allow the inference of
the regular language $(ab)^{*}$, and the automaton derived from $\mathcal{S}$.
We note that the last three examples could be dropped, and the set would still
be sufficient.

In the following, let $L$ be a regular language, $\mathcal{S}$ a sufficient
example for $L$, and $\sim_{\mathcal{S}}$ the smallest equivalence relation on
$\mathit{str}(\mathcal{S})$ such that $w\sim_{\mathcal{S}}w^{\prime}$ for all
$w,w^{\prime}\in\mathit{str}(\mathcal{S})$ such that $\mathcal{S}$ contains
the example $(\mathit{equiv}(x,y),\\{w,w^{\prime}\\})$.

######  Lemma 4.1.

If $B\in(\Xi^{*}/{\sim_{L}})$ is live then for every
$(D,\xi)\in\mathit{pred}(B)$,
$D\xi\cap\mathit{prefixes}(\mathcal{S})\not=\emptyset$.

######  Proof 4.2.

If $B$ is a convergence, the statement of Lemma 4.1 is immediately fulfilled
by Condition 2b. Assume then that this is not the case, and choose some
arbitrary string $v\in B$. We cannot have $B=[\varepsilon]_{\sim_{L}}$ because
then the assumption that $B$ is not a convergence implies that
$\mathit{pred}(B)=\emptyset$. Since $B$ is live, there is a string $w$ such
that $[vw]_{\sim_{L}}$ is a convergence or a subset of $L$. Let $w$ be such a
string of minimal length (this can be $0$). Because of the minimality of $w$
there must be a string $u\in B$ such that $uw\in\mathit{str}(\mathcal{S})$.
Since $\varepsilon\notin B$, we have $u=u_{0}\xi$ for some
$u_{0}\in\mathit{prefixes}(\mathcal{S})$ and $\xi\in\Xi$. Then
$\mathit{pred}(B)=\\{([u_{0}]_{\sim_{L}},\xi)\\}$, which completes the proof.

######  Definition 4.3.

Let $S\subseteq\Xi^{*}$, and let $\sim$ be an equivalence relation on $S$. The
_right completion_ of $\sim$ is the smallest equivalence relation
${\sim^{\mathrm{rc}}}\supseteq{\sim}$ on $\mathit{prefixes}(S)$ such that, for
all $w\xi,w^{\prime}\xi\in\mathit{prefixes}(S)$ (where
$w,w^{\prime}\in\Xi^{*}$ and $\xi\in\Xi$), if $w\sim^{\mathrm{rc}}w^{\prime}$
then $w\xi\sim^{\mathrm{rc}}w^{\prime}\xi$.

Note that, for finite $S$, the set $E$ of equivalence classes of
$\sim^{\mathrm{rc}}$ (and thus $\sim^{\mathrm{rc}}$ itself) can be computed
from $\sim$ in a standard manner: initially,
$E=(\mathit{prefixes}(S)/{\sim})$. Now, while there exists distinct
$C,C^{\prime}\in E$ such that there are $w\xi\in C$ and $w^{\prime}\xi\in
C^{\prime}$ such that $w\sim^{\mathrm{rc}}w^{\prime}$, we let
$E\leftarrow(E\setminus\\{C,C^{\prime}\\})\cup\\{C\cup C^{\prime}\\}$.

We have the following lemma:

######  Lemma 4.4.

${\sim^{\mathrm{rc}}_{\mathcal{S}}}={\sim_{L}}\cap(\mathit{prefixes}(\mathcal{S})\times\mathit{prefixes}(\mathcal{S}))$.

######  Proof 4.5.

Since right completion is monotone and
${\sim_{\mathcal{S}}}\subseteq{\sim_{L}}$, we have
${\sim^{\mathrm{rc}}_{\mathcal{S}}}\subseteq{\sim^{\mathrm{rc}}_{L}}={\sim_{L}}$,
where the equality holds because $\sim_{L}$ is a right congruence. Here,
${\sim^{\mathrm{rc}}_{\mathcal{S}}}\subseteq\mathit{prefixes}(\mathcal{S})\times\mathit{prefixes}(\mathcal{S})$,
and thus
${\sim^{\mathrm{rc}}_{\mathcal{S}}}={\sim^{\mathrm{rc}}_{\mathcal{S}}}\cap(\mathit{prefixes}(\mathcal{S})\times\mathit{prefixes}(\mathcal{S}))\subseteq{\sim_{L}}\cap(\mathit{prefixes}(\mathcal{S})\times\mathit{prefixes}(\mathcal{S}))$.

For the other inclusion, assume that
$w,w^{\prime}\in\mathit{prefixes}(\mathcal{S})$ are such that
$w\sim_{L}w^{\prime}$. Due to Condition 2b, $w$ and $w^{\prime}$ must either
both be in $\mathit{str}(\mathcal{S})$ or both be in
$\mathit{prefixes}(\mathcal{S})\setminus\mathit{str}(\mathcal{S})$. If they
are in $\mathit{str}(\mathcal{S})$, then by Condition 3,
$w\sim_{\mathcal{S}}^{\star}w^{\prime}$. If they are in
$\mathit{prefixes}(\mathcal{S})\setminus\mathit{str}(\mathcal{S})$, then they
must be of the form $u\xi,u^{\prime}\xi$ for some
$u,u^{\prime}\in\mathit{prefixes}(\mathcal{S})$ with $u\sim_{L}u^{\prime}$, or
else $[w]_{\sim_{L}}$ would constitute a convergence and thus
$w,w^{\prime}\in\mathit{str}(\mathcal{S})$. Assume that $w,w^{\prime}$ are of
minimal length with this property. Then
$u\sim^{\mathrm{rc}}_{\mathcal{S}}u^{\prime}$, but this cannot be because
$w,w^{\prime}\in\mathit{prefixes}(\mathcal{S})$ and thus
$w\sim^{\mathrm{rc}}_{\mathcal{S}}w^{\prime}$ by Definition 4.3.

######  Definition 4.6 (DFA construction).

Let $S\subseteq\Xi^{*}$, let $\sim$ be an equivalence relation on $S$, and let
$F\subseteq S$. The DFA $\textsc{Aut}(S,\sim,F)$ is given by
$(\Xi,Q,\delta,q_{0},Q_{F})$ where

  * •

$Q=(\mathit{prefixes}(S)/{\sim})$,

  * •

$\delta$ is the partial transition function such that $\delta(B,\xi)$ is
defined and equal to $B^{\prime}\in Q$ if $w\xi\in B^{\prime}$ for some $w\in
B$,

  * •

$q_{0}=[\varepsilon]^{\mathit{prefixes}(S)}_{\sim}$, and

  * •

$Q_{F}=\\{B\in Q\mid B\cap F\neq\emptyset\\}$.

With the preceding definition, we can now use $\mathcal{S}$ to build a DFA
that recognises $L$:

######  Lemma 4.7.

Let
$F_{\mathcal{S}}=\\{w\in\mathit{str}(\mathcal{S})\mid(\mathit{accept}[x],\\{w\\})\in\mathcal{S}\\}$.
Then the DFA
$M_{\mathcal{S}}=\textsc{Aut}(\mathit{prefixes}(\mathcal{S}),\sim^{\mathrm{rc}}_{\mathcal{S}},F_{\mathcal{S}})$
is isomorphic to $M_{L}$.

######  Proof 4.8.

Let $M_{L}=(\Xi,Q^{\prime},\delta^{\prime},q_{0}^{\prime},F^{\prime})$ and
$M_{\mathcal{S}}=(\Xi,Q,\delta,q_{0},F)$. By Lemma 4.4,
${\sim^{\mathrm{rc}}_{\mathcal{S}}}\subseteq{\sim_{L}}$, so every state $q\in
Q$ is a subset of some (by Lemma 4.1 live) congruence class in
$(\Xi^{*}/{\sim_{L}})$, i.e., of a state $q^{\prime}\in Q^{\prime}$. Also by
Lemma 4.4, $w\not\sim^{\mathrm{rc}}_{\mathcal{S}}w^{\prime}$ implies
$w\not\sim_{L}w^{\prime}$. Hence, the mapping $\pi\colon Q\to Q^{\prime}$ such
that $q\subseteq\pi(q)$ for all $q\in Q$ is well defined and injective.

Lemma 4.1 together with the constructions of $\delta$ and $\delta^{\prime}$
(via Definition 4.6 and the Myhill-Nerode construction, respectively), yield
the following for all $q\in Q$ and $\xi\in\Xi$: $\delta(q,\xi)$ is defined if
and only if $\delta^{\prime}(\pi(q),\xi)$ is defined, and in this case it
holds that $\delta^{\prime}(\pi(q),\xi)=\pi(\delta(q,\xi))$. Moreover,
$\pi(q_{0})=q_{0}^{\prime}$ because $\varepsilon\in q_{0}\cap q_{0}^{\prime}$.
Finally, a state $q\in Q$ is in $F$ if and only if $q\cap
F_{\mathcal{S}}\neq\emptyset$, which by the definition of $F_{\mathcal{S}}$
and Condition 2a is the case if and only if $\pi(q)\cap L\neq\emptyset$. Again
by the fact that $M_{L}$ results from the Myhill-Nerode construction, the
latter is equivalent to $\pi(q)\in F^{\prime}$. Hence, altogether,
$M_{\mathcal{S}}$ and $M_{L}$ are isomorphic.

Note that the construction of $M_{\mathcal{S}}$ does not depend on the
existence of distinguishing examples according to Condition 4. While this
means that $M_{\mathcal{S}}$ would stay unchanged even if those examples would
be absent, the theorem we prove now would fail.

######  Theorem 4.9.

Let $L$ be a regular language and $M_{L}=(\Xi,Q,\delta,q_{0},F)$. Then
maximizes (2). Furthermore, it is minimal in the following sense: if
$M=(\Xi,Q^{\prime},\delta^{\prime},q_{0}^{\prime},F^{\prime})$ is another DFA
such that maximizes (2), then there is an injective mapping $\pi\colon Q\to
Q^{\prime}$ such that $\pi(q_{0})=q_{0}^{\prime}$,
$\delta^{\prime}(\pi(q),\xi)=\pi(\delta(q,\xi))$ for all
$(q,\xi)\in\mathrm{dom}(\delta)$, and $\pi(F)\subseteq F^{\prime}$. In
particular, $L\subseteq L(M^{\prime})$.

######  Proof 4.10.

It is straightforward to verify that the instantiation ensures that all
examples attain the value $\mathrm{true}$. Hence, maximizes (2).

For the rest of the proof, let
$M_{\mathcal{S}}=\textsc{Aut}(\mathit{prefixes}(\mathcal{S}),\sim^{\mathrm{rc}}_{\mathcal{S}},F_{\mathcal{S}})$.
By Lemma 4.7 we prove the statement of the theorem for
$M_{\mathcal{S}}=(\Xi,Q,\delta,q_{0},F)$ instead of $M_{L}$, i.e., the states
are subsets of $\mathit{prefixes}(\mathcal{S})$ instead of congruence classes
of $(\Xi^{*}/{\sim_{L}})$. Let $M$ be another DFA, as in the statement of the
theorem. Instead of $M$, we shall for the time being consider the canonical
_total_ DFA
$M_{0}=(\Xi,Q_{0}^{\prime},\delta_{0}^{\prime},q_{0}^{\prime},F^{\prime})$
recognising $L(M)$. Thus, we can assume that $M$ is obtained from $M_{0}$ by
removing the sink state if there is one, and $M=M_{0}$ otherwise.

Every state $q\in Q$ is a subset of a state in $Q_{0}^{\prime}$ because  (a)
for all $w,w^{\prime}\in\mathit{prefixes}(\mathcal{S})$ the implications
$w\sim_{\mathcal{S}}w^{\prime}\Rightarrow(\mathit{equiv}(x,y),\\{w,w^{\prime}\\})\in\mathcal{S}\Rightarrow
w\sim_{L(M_{0})}w^{\prime}$ hold (the latter since $M$ maximises (2)),  (b)
$\sim_{L(M_{0})}$is a right congruence and  (c)
$\sim^{\mathrm{rc}}_{\mathcal{S}}$is the smallest right equivalence on
$\mathit{prefixes}(\mathcal{S})$ that contains $\sim_{\mathcal{S}}$.

Let thus $\pi\colon Q\to Q_{0}^{\prime}$ be the mapping such that
$q\subseteq\pi(q)$ for all $q\in Q$. Then $\pi$ is injective: if there would
be two distinct states $q,q^{\prime}\in Q$ such that
$q^{\prime}\subseteq\pi(q)$ then $M_{0}$ (and thus $M$) would fail to satisfy
one of the examples $(\neg\mathit{equiv}(x,y),O)$ contained in $\mathcal{S}$
owing to Condition 4, and would thus not maximise (2). Furthermore, by
Condition 2a we have $\pi(q)\in F_{\mathcal{S}}$ for all $q\in F$, and since
$\varepsilon\in q_{0}\cap q_{0}^{\prime}$, we also have
$\pi(q_{0})=q_{0}^{\prime}$.

Now recall that $\delta_{0}^{\prime}$ is the transition function defined by
the Myhill-Nerode construction. Thus, for all $q\in Q_{0}$, $w\in\Xi^{*}$, and
$\xi\in\Xi$ it holds that $\delta_{0}^{\prime}(q,a)=q^{\prime}$ if $wa\in
q^{\prime}$. Since this is just how $\delta$ is defined, it follows that
$\delta_{0}(\pi(q),\xi)=\pi(\delta(q,\xi))$ for all
$(q,\xi)\in\mathrm{dom}(\delta)$. In particular, all states of the form
$\pi(q)$, $q\in Q$, are live in $M_{0}$ because they are so in
$M_{\mathcal{S}}$. Consequently, $\pi$ actually maps $Q$ to $Q^{\prime}$,
which completes the proof.

###  4.2 Picture Languages

The second example instantiation of the algebraic framework allows us to infer
picture languages of the type described by Drewes (2006). These language are
generated by grammatical systems whose rules transform and combine images to
more complex ones: A _collage grammar_ is a pair $G=(g,\mathcal{C})$
consisting of  (1) a regular tree grammar $g$ such that $L(g)\subseteq p$ for
some type $p$ and a $\\{p\\}$-typed alphabet $\Sigma$, and  (2) a so-called
collage algebra $\mathcal{C}=(\mathbb{C},(F_{\mathcal{C}})_{F\in\Sigma})$.
The components of such a collage algebra $\mathcal{C}$ are given as follows:

  * •

$\mathbb{C}$ is the set of all compact subsets of 2, here referred to as
_pictures_.222A subset of 2 is compact if it is bounded (a subset of a disc)
and contains all limits of Cauchy sequences in it.

  * •

The interpretation of every $F\colon p$ in $\Sigma$ is an element
$F_{\mathcal{C}}$ of $\mathbb{C}$.

  * •

The interpretation of every $F\colon p^{k}\to p$ with $k>1$, is given by $k$
affine transformation $f_{1},\dots,f_{k}$ of 2, as follows:
$F_{\mathcal{C}}(C_{1},\dots,C_{k})=\bigcup_{i\in[k]}f_{i}(C_{i})$. Thus, $F$
transforms its $i$th argument by $f_{i}$ and returns the union of the
resulting $k$ pictures. We also denote such a function $F_{\mathcal{C}}$ by
$\langle f_{1}\cdots f_{k}\rangle$.

The language generated by $G$ is $L(G)=\\{\mathrm{val}_{\mathcal{C}}(t)\mid
t\in L(g)\\}$.

An example of a collage grammar $G=(g,\mathcal{C})$ is depicted in Figure 2.

$\begin{array}[]{<EMAIL_ADDRESS>converted-to.pdf}}\ \to\
\raisebox{-21.33955pt}{\includegraphics[width=42.67912pt]{treebag/grid/chair/ps/rhsS-
eps-converted-to.pdf}}\\\ \\\\[0.0pt]
\raisebox{-21.33955pt}{\includegraphics[width=42.67912pt]{treebag/grid/chair/ps/A-eps-
converted-to.pdf}}\ \to\
\raisebox{-21.33955pt}{\includegraphics[width=42.67912pt]{treebag/grid/chair/ps/rhsA1-eps-
converted-
to.pdf}}\quad\rule[-21.33955pt]{0.5pt}{46.94728pt}\quad\raisebox{-21.33955pt}{\includegraphics[width=42.67912pt]{treebag/grid/chair/ps/rhsA2-eps-
converted-to.pdf}}\\\ \\\\[0.0pt]
\raisebox{-21.33955pt}{\includegraphics[width=42.67912pt]{treebag/grid/chair/ps/B-eps-
converted-to.pdf}}\ \to\
\raisebox{-21.33955pt}{\includegraphics[width=42.67912pt]{treebag/grid/chair/ps/rhsB1-eps-
converted-
to.pdf}}\quad\rule[-21.33955pt]{0.5pt}{46.94728pt}\quad\raisebox{-21.33955pt}{\includegraphics[width=42.67912pt]{treebag/grid/chair/ps/rhsB2-eps-
converted-to.pdf}}\end{array}$
$\begin{array}[]{<EMAIL_ADDRESS>converted-to.pdf}\end{array}$

Figure 2: Graphical illustration of a collage grammar (left) and one of the
generated pictures (right). The rules of the regular tree grammar are $S\to
F[A,A,A,A]$ (top), $A\to F[A,A,A,A]\mid F[B,B,B,B]$ (middle), and $B\to
G[C,S]\mid C$ (bottom), separating alternative right-hand sides for the same
left-hand side by ‘$\mid$’. To obtain the graphical illustration of the rules
and, at the same time, indicate the transformations constituting $F$ and $G$
(and the picture $C$), the algebra was extended to interpret $S$, $A$, and $B$
as squares with an inscribed nonterminal name and L-shape making orientation
unambiguous. (Colours just serve better visual distinction.) The initial
nonterminal is $S$.

Suppose we want to learn $G$ from examples. We obviously have to learn both
$g$ and the interpretation of the symbols appearing in the terms in $L(g)$,
i.e., we have to learn $\mathcal{C}$. Learning $g$ is an interesting task that
has been considered in many research articles. However, since this problem is
similar to Section 4.1, we do not consider it here, focusing instead on the
second component. We discuss one way in which our framework can be used to
formalise and study this learning task.

Consider the operation $F_{\mathcal{C}}=\langle
f_{1},f_{2},f_{3},f_{4}\rangle$ in our example. To learn it, we need to learn
each of the affine transformations $f_{i}$ defining it. By the definition of
affine transformations, $f_{i}(x)=M_{i}x+b_{i}$ where $M_{i}$ is a $2\times 2$
matrix with real coefficients and $b\in^{2}$. This is just the type of mapping
a single linear layer of a neural network $\mathcal{N}$ can implement. Hence,
we propose to use our framework to study how this can be done. For the
learning, we may assume that all operations except $F$ are known, i.e., we
consider the template algebra $\mathcal{C}^{\prime}$ which is equal to
$\mathcal{C}$ with the exception that $F_{\mathcal{C}^{\prime}}$ is undefined.
We can use the regular tree grammar $g$ to generate examples from which the
network is supposed to learn $F$. Intuitively, each example is a pair
consisting of a term and its evaluation according to $\mathcal{C}$. However,
this does not yet fulfil the requirements of our general definition. What is
missing is a way to measure how good a job $\mathcal{N}$ does. In other words,
we need a distance measure on $\mathbb{C}$. For this, we may for example use
the well-known Hausdorff measure (Hausdorff, 1918), the more recent Earth
Mover's distance by Rubner et al. (2000), or, if we restrict ourselves to
pictures consisting of finite unions of simple geometric shapes, the area of
the symmetric difference between pictures. Let $\delta$ denote such a distance
measure, and let $\mathcal{C}_{\delta}$ be $\mathcal{C}$ extended by this
operation, which is of type $\delta\colon\mathbb{C}\mathbb{C}\to$. (For
simplicity, we blur the distinction between the symbol $\delta$ and its
interpretation.) Now, to stay within our framework, we can use examples of the
form $(\delta[x_{1},t],\mathrm{val}_{\mathcal{C}}(t))$, where $t\in L(g)$. In
fact, as long as we are not concerned with learning $g$ as well, the
requirement that $t\in L(g)$ is superfluous. Furthermore, we can enrich
$\mathcal{C}^{\prime}$ with further shapes than only $C$, making it possible
to use examples that simplify learning.

Thus, to experiment with how well $\mathcal{N}$ can learn $F_{\mathcal{C}}$,
we may generate a corpus of such examples and train $\mathcal{N}$, using as a
loss function the average of the losses of individual examples. Let
$\mathcal{C}_{\mathcal{N}}$ denote the algebra obtained from
$\mathcal{C}^{\prime}$ by interpreting $F$ according to $\mathcal{N}$. The
loss of a single example $(\delta[x_{1},t],C)$ is then
$\delta(C,\mathrm{val}_{\mathcal{C}_{\mathcal{N}}}(t))$. An example of a set
of four examples using triangles and squares as basic pictures is shown in
Figure 3 at the top.

$\begin{array}[]{@{}c@{\qquad}c@{\qquad}c@{\qquad}c@{}}F[\mathit{tri},\mathit{sq},\mathit{tri},\mathit{sq}]&F[\mathit{tri},\mathit{tri},\mathit{sq},\mathit{sq}]&F[\mathit{sq},\mathit{tri},\mathit{sq},\mathit{tri}]&F[\begin{array}[t]{@{}l@{}}F[\mathit{tri},\mathit{sq},\mathit{tri},\mathit{sq}],\\\
\mathit{tri},\mathit{tri},\mathit{sq}]\end{array}\\\
\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample1-eps-converted-
to}&\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample2-eps-converted-
to}&\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample3-eps-converted-
to}&\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample4-eps-converted-
to}\\\ \\\\[0.0pt]
\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample1-overlay1-eps-
converted-
to}&\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample2-overlay1-eps-
converted-
to}&\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample3-overlay1-eps-
converted-
to}&\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample4-overlay1-eps-
converted-to}\\\ \\\\[0.0pt]
\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample1-overlay2-eps-
converted-
to}&\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample2-overlay2-eps-
converted-
to}&\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample3-overlay2-eps-
converted-
to}&\includegraphics[scale={.05}]{treebag/grid/chair/ps/sample4-overlay2-eps-
converted-to}\end{array}$

Figure 3: Top: four examples, where the first component of each example
$(\delta(x_{1},t),\mathrm{val}_{\mathcal{C}}(t))$ has been shortened to $t$.
Middle: overlay of each $\mathrm{val}_{\mathcal{C}}(t)$ (black) and the
corresponding $\mathrm{val}_{\mathcal{C}_{\mathcal{N}}}(t)$ (grey) for some
imperfect approximation of $F_{\mathcal{C}}$ by an imaginary neural network
$\mathcal{N}$. Bottom: similar overlay after a slight adjustment of the
transformation parameters.

As indicated in the second and third row of the figure, training $\mathcal{N}$
should reduce the distance between $\mathrm{val}_{\mathcal{C}}(t)$ and
$\mathrm{val}_{\mathcal{C}_{\mathcal{N}}}(t)$, ideally until the pictures
match perfectly. However, there is an interesting problem here for future
research: For learning neural networks by back propagation, the loss function
should be differentiable in each parameter of the network, i.e., in this case
in each of the six parameters of each of the affine transformations involved.
While the loss is easily seen to be continuous, it is not necessarily
differentiable. Hence, it would be an interesting research question to find
out whether this difficulty can be circumvented, for example by techniques
such as those proposed by Grabocka et al. (2019) and Lee et al. (2020). Even
in cases where the loss is differentiable, another open problem is how to
actually compute the partial derivatives. We leave these questions for future
work because the purpose of the current paper is to propose the unified
framework and motivate it by examples.

###  4.3 Scene descriptions

$\begin{bmatrix}1.2\\\\[1.93748pt] 3.6\\\\[1.93748pt] \vdots\\\\[2.71246pt]
3.5\end{bmatrix}$$o_{1}$$\begin{bmatrix}3.4\\\\[1.93748pt] 1.8\\\\[1.93748pt]
\vdots\\\\[2.71246pt]
3.9\end{bmatrix}$$o_{2}$$\begin{bmatrix}1.2\\\\[1.93748pt] 9.0\\\\[1.93748pt]
\vdots\\\\[2.71246pt]
8.1\end{bmatrix}$$o_{3}$$\begin{bmatrix}7.1\\\\[1.93748pt] 8.0\\\\[1.93748pt]
\vdots\\\\[2.71246pt]
0.8\end{bmatrix}$$o_{4}$$\begin{bmatrix}1.4\\\\[1.93748pt] 2.2\\\\[1.93748pt]
\vdots\\\\[2.71246pt] 6.6\end{bmatrix}$$o_{5}$$\varphi=r(x)\land b(x)\land
r(y)\land g(y)$ Figure 4: To predicates in a scene, the scene is first
segmented into a set of objects, each of which is translated into a real-
valued vector $o$. If the neural networks that realise the predicates of
$\varphi$ have been satisfactorily trained, then there is an assignment of
objects to the variables that satisfies $\varphi$. In this example, the
predicates $r$, $b$, and $g$ can be understood as the properties of being
round, being bronze coloured, and being gold coloured, respectively. Under
this interpretation, the assignment of $o_{2}$ to $x$ and $o_{5}$ to $y$
satisfies $\varphi$.

The final instantiation of the algebraic framework serves to learn (predicates
representing) properties of physical objects, so as to be able to ground the
variables of a logic scene description in a scene. For simplicity, we limit
the discussion to the type of synthetic scenes provided by Johnson et al.
(2017) through the CLEVR dataset. In this dataset, a scene is a configuration
of a limited number of geometrical objects of different shapes, colors,
materials, and sizes. For the present, we also disregard the relative
positioning of objects within the scene, even though such relations could be
modelled by an extension of the logic described in the following. A final
simplification is the assumption that the scene has already been segmented and
every object found has been translated into a real-valued vector $o$ by a
pretrained visual embedding model. A scene is thus represented as a multiset
of such vectors, and these multisets take the place of the objects in
examples.

An example $(\varphi,O)$ consists of a multiset of object vectors $O$ and a
term $\varphi$ representing a logic formula over unary predicates, logical
connectives, and free variables. The predicates represent properties of
objects, and the example provides an example of a true property (expressed by
$\varphi$) of the scene object $O$, for some assignment of scene objects to
the variables. An example is shown in Figure 4, where the objects in the scene
have been translated into vector-based embeddings. The goal is to use the
examples in order to discover the meaning of the predicates.

Let us now formalise this setting in our framework. For this, let
$\Gamma=\\{\alpha,\beta\\}$ and $\Sigma=C\cup P$ with

$C=\\{\land
\colon\beta\times\beta\to\beta,\;\lor\colon\beta\times\beta\to\beta,\;\rightarrow\colon\beta\times\beta\to\beta,\;\lnot\colon\beta\to\beta\\}$

and $P=\\{p\colon\alpha\to\beta,\;\dots,\;p_{n}\colon\alpha\to\beta\\}$.
Moreover, $X$ is a set of variables, all of type $\alpha$. Let , where
${\mathbb{A}}_{\alpha}=^{n}$ and ${\mathbb{A}}_{\beta}=[0,1]$, the latter
denoting the unit interval of real numbers. Our evaluation domain is
${\mathbb{A}}_{\beta}$ with the usual order on $[0,1]$, and $\bigoplus V=\sum
V/|V|$ is the average of $V$ for every finite subset $V$ of $[0,1]$. The
interpretation of the logical connectives $f$ for $f\in\Sigma\backslash P$ is
given in Table 1. In this template algebra, it is possible to use neural
networks to model the to be learned predicates in $P$. These predicates map
object embeddings to real numbers, where the value signals that the input
object has a certain property (according to the neural network implementing
the predicate), and a lower value signals that it does not. Since the learning
goal is to maximise the total value $\bigoplus_{O\in\mathcal{S}}\mathrm{val}$
of all examples in the example set $\mathcal{S}$, we can use $1-\mathrm{val}$
as the loss function for training. Given a finite set $\mathcal{S}$ of
examples, the sum in Equation (1) can then be maximised by training a family
of neural networks $(\theta_{p})_{p\in P}$ to realise the set of predicates
$P$.

Table 1: Algebraic operations to model logic connectives for scene grounding $\land$ | = |  $\textrm{min}(n_{1},n_{2})$ | $\lor$ | = | $\textrm{max}(n_{1},n_{2})$
---|---|---|---|---|---
$\rightarrow$ | = |  $\textrm{max}(1-n_{1},n_{2})$ | $\lnot$ | = | $1-n_{1}$

The natural continuation of this theoretical work is an empirical study
starting out from a more or less abstract representation of objects. For
example, this could be a real-valued vector produced by applying an out-of-
the-box autoencoder to the segmented object. One would then generate a set of
training examples $\\{(\varphi_{1},O_{1}),\dots,(\varphi_{n},O_{n})\\}$ for
some $n\in{\rm Nature}$, and train the neural networks $(\theta_{p})_{p\in
P}$.

##  5 Conclusion and future work

We have introduced an algebraic framework that can be instantiated for a
variety of learning settings, allowing us to integrate grammatical inference
and deep-learning approaches. As indicated throughout the paper, this is an
initial theoretical effort, but framework lends itself well to empirical
experiments, and this is also the the natural next step. One of the main
advantages of the algebraic approach is that it allows us to look at a
learning setting through a layer of abstraction. This makes it possible to
treat various aspects in isolation, and opens for a wealth of research
directions.

In general, we may ask what properties of the algebraic domains and operations
promote learning. We may also consider the effect of different valuation
schemes, e.g., should we allow that two variables are assigned the same logic
object, or require that every object is assigned to some variable. We may also
study the effect of adding universal and existential quantifiers, and so
requiring that certain properties hold for all or some of the elements in an
example. Another question is the trade-off between computational complexity
and expressiveness that comes from learning predicates of arity greater than
one. Such an addition would allow us to learn relations, e.g., whether one
object is smaller than another, but would doubtlessly also require greater
computational effort.

In the cases where we apply deep learning, it is natural to explore different
forms of object representations and network architectures, but also the
realisation of logic connectives in a numerical domain. Finally, we may also
consider how we can manage a situation where the number of elements in an
example is very large (consider, e.g., a painting of a city scene in great
detail). Here, it may not be feasible to try every possible way of linking the
variables in the accompanying formula to a segment of the scene, so one may
devise various heuristics of limiting the number of combinations to evaluate.

## References

  * Antol et al. (2015) Stanislaw Antol, Aishwarya Agrawal, Jiasen Lu, Margaret Mitchell, Dhruv Batra, C Lawrence Zitnick, and Devi Parikh.  VQA: Visual question answering.  In _Proceedings of the IEEE international conference on computer vision_ , pages 2425–2433, 2015.
  * Badreddine et al. (2022) Samy Badreddine, Artur d'Avila Garcez, Luciano Serafini, and Michael Spranger.  Logic tensor networks.  _Artificial Intelligence_ , 303:103649, 2022.
  * Bender and Koller (2020) Emily M Bender and Alexander Koller.  Climbing towards nlu: On meaning, form, and understanding in the age of data.  In _Proceedings of the 58th Annual Meeting of the Association for Computational Linguistics_ , pages 5185–5198, 2020.
  * Bender et al. (2021) Emily M Bender, Timnit Gebru, Angelina McMillan-Major, and Shmargaret Shmitchell.  On the dangers of stochastic parrots: Can language models be too big?  In _Proceedings of the 2021 ACM Conference on Fairness, Accountability, and Transparency_ , pages 610–623, 2021.
  * Chaplot et al. (2018) Devendra Singh Chaplot, Kanthashree Mysore Sathyendra, Rama Kumar Pasumarthi, Dheeraj Rajagopal, and Ruslan Salakhutdinov.  Gated-attention architectures for task-oriented language grounding.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Cropper et al. (2022) Andrew Cropper, Sebastijan Dumančić, Richard Evans, and Stephen H Muggleton.  Inductive logic programming at 30.  _Machine Learning_ , 111(1):147–172, 2022.
  * Dai et al. (2015) Wang-Zhou Dai, Stephen H Muggleton, and Zhi-Hua Zhou.  Logical vision: Meta-interpretive learning for simple geometrical concepts.  In _ILP (Late Breaking Papers)_ , 2015.
  * Dantsin (1992) Eugene Dantsin.  Probabilistic logic programs and their semantics.  In _Logic Programming_ , pages 152–164. Springer, 1992.
  * de la Higuera (1997) Colin de la Higuera.  Characteristic sets for polynomial grammatical inference.  _Machine Learning_ , 27:125–138, 1997.
  * De Raedt et al. (2007) Luc De Raedt, Angelika Kimmig, and Hannu Toivonen.  Problog: A probabilistic prolog and its application in link discovery.  In _Proceedings of the 20th International Joint Conference on Artificial Intelligence_ , pages 2462–2467, 2007.
  * Donadello et al. (2017) Ivan Donadello, Luciano Serafini, and Artur D'Avila Garcez.  Logic tensor networks for semantic image interpretation.  In _Proceedings of the 26th International Joint Conference on Artificial Intelligence_ , pages 1596–1602, 2017.
  * Drewes (2006) Frank Drewes.  _Grammatical Picture Generation – A Tree-Based Approach_.  Texts in Theoretical Computer Science. An EATCS Series. Springer, 2006\.
  * Erdem et al. (2016) Esra Erdem, Michael Gelfond, and Nicola Leone.  Applications of answer set programming.  _AI Magazine_ , 37(3):53–68, 2016.
  * Fukui et al. (2016) Akira Fukui, Dong Huk Park, Daylen Yang, Anna Rohrbach, Trevor Darrell, and Marcus Rohrbach.  Multimodal compact bilinear pooling for visual question answering and visual grounding.  In _Proceedings of the 2016 Conference on Empirical Methods in Natural Language Processing_ , pages 457–468, November 2016.
  * Garcez et al. (2019) Artur Garcez, Marco Gori, Luís C. Lamb, Luciano Serafini, Michael Spranger, and Son N. Tran.  Neural-symbolic computing: An effective methodology for principled integration of machine learning and reasoning.  _Journal of Applied Logics_ , 6(4):611–631, 2019\.
  * Grabocka et al. (2019) Josif Grabocka, Randolf Scholz, and Lars Schmidt-Thieme.  Learning surrogate losses.  _arXiv:1905.10108_ , 2019.
  * Hausdorff (1918) Felix Hausdorff.  Dimension und äußeres Mass.  _Mathematische Annalen_ , 79:157–179, 1918.
  * Hudson and Manning (2019) Drew Hudson and Christopher D Manning.  Learning by abstraction: The neural state machine.  _Advances in Neural Information Processing Systems_ , 32, 2019.
  * Johnson et al. (2017) Justin Johnson, Bharath Hariharan, Laurens van der Maaten, Li Fei-Fei, C. Lawrence Zitnick, and Ross B. Girshick.  Clevr: A diagnostic dataset for compositional language and elementary visual reasoning.  In _2017 IEEE Conference on Computer Vision and Pattern Recognition (CVPR)_ , pages 1988–1997, 2017.
  * Lee et al. (2020) Wonyeol Lee, Hangyeol Yu, Xavier Rival, and Hongseok Yang.  On correctness of automatic differentiation for non-differentiable functions.  In _Advances in Neural Information Processing Systems_ , volume 33, 2020.
  * Lifschitz (2002) Vladimir Lifschitz.  Answer set programming and plan generation.  _Artificial Intelligence_ , 138(1-2):39–54, 2002\.
  * Manhaeve et al. (2018) Robin Manhaeve, Sebastijan Dumancic, Angelika Kimmig, Thomas Demeester, and Luc De Raedt.  Deepproblog: Neural probabilistic logic programming.  In S. Bengio, H. Wallach, H. Larochelle, K. Grauman, N. Cesa-Bianchi, and R. Garnett, editors, _Advances in Neural Information Processing Systems_ , volume 31, 2018.
  * Mao et al. (2019) Jiayuan Mao, Chuang Gan, Pushmeet Kohli, Joshua B. Tenenbaum, and Jiajun Wu.  The Neuro-Symbolic Concept Learner: Interpreting Scenes, Words, and Sentences From Natural Supervision.  In _International Conference on Learning Representations_ , 2019.
  * Marek and Truszczyński (1999) Victor W Marek and Miroslaw Truszczyński.  Stable models and an alternative logic programming paradigm.  In _The Logic Programming Paradigm_ , pages 375–398. Springer, 1999\.
  * Muggleton and De Raedt (1994) Stephen Muggleton and Luc De Raedt.  Inductive logic programming: Theory and methods.  _The Journal of Logic Programming_ , 19:629–679, 1994.
  * Ng and Subrahmanian (1992) Raymond Ng and Venkatramanan Siva Subrahmanian.  Probabilistic logic programming.  _Information and computation_ , 101(2):150–201, 1992.
  * Niemelä (1999) Ilkka Niemelä.  Logic programs with stable model semantics as a constraint programming paradigm.  _Annals of mathematics and Artificial Intelligence_ , 25(3):241–273, 1999.
  * Oncina and Garcia (1992) José Oncina and Pedro Garcia.  Inferring regular languages in polynomial updated time.  In _Pattern recognition and image analysis: selected papers from the IVth Spanish Symposium_ , pages 49–61. World Scientific, 1992.
  * Raedt and Kersting (2008) Luc De Raedt and Kristian Kersting.  Probabilistic inductive logic programming.  In _Probabilistic inductive logic programming_ , pages 1–27. Springer, 2008.
  * Rubner et al. (2000) Yossi Rubner, Carlo Tomasi, and Leonidas J Guibas.  The earth mover's distance as a metric for image retrieval.  _International journal of computer vision_ , 40(2):99–121, 2000.
  * Serafini and Garcez (2016) Luciano Serafini and Artur d'Avila Garcez.  Logic tensor networks: Deep learning and logical reasoning from data and knowledge.  _arXiv:1606.04422_ , 2016.
  * Suchan et al. (2018) Jakob Suchan, Mehul Bhatt, Przemysław Wałega, and Carl Schultz.  Visual explanation by high-level abduction: On answer-set programming driven reasoning about moving objects.  In _Proceedings of the AAAI Conference on Artificial Intelligence_ , volume 32, 2018.
  * Varghese et al. (2021) Dany Varghese, Roman Bauer, Daniel Baxter-Beard, Stephen Muggleton, and Alireza Tamaddoni-Nezhad.  Human-like rule learning from images using one-shot hypothesis derivation.  In _International Conference on Inductive Logic Programming_ , pages 234–250. Springer, 2021.
  * Weber et al. (2019) Leon Weber, Pasquale Minervini, Jannes Münchmeyer, Ulf Leser, and Tim Rocktäschel.  Nlprolog: Reasoning with weak unification for question answering in natural language.  In _Proceedings of the 57th Annual Meeting of the Association for Computational Linguistics_ , pages 6151–6161, 2019.
  * Winters et al. (2021) Thomas Winters, Giuseppe Marra, Robin Manhaeve, and Luc De Raedt.  Deepstochlog: Neural stochastic logic programming.  _arXiv:2106.12574_ , 2021.
  * Yi et al. (2018) Kexin Yi, Jiajun Wu, Chuang Gan, Antonio Torralba, Pushmeet Kohli, and Josh Tenenbaum.  Neural-symbolic vqa: Disentangling reasoning from vision and language understanding.  _Advances in neural information processing systems_ , 31, 2018.