# Galois theory for analogical classifiers

Miguel Couceiro  Université de Lorraine, CNRS, LORIA
F-54000 Nancy
France  and  Erkko Lehtonen  Centro de Matemática e Aplicações
Faculdade de Ciências e Tecnologia
Universidade Nova de Lisboa
Quinta da Torre
2829-516 Caparica
Portugal

###### Abstract.

Analogical proportions are 4-ary relations that read “A is to B as C is to D”.
Recent works have highlighted the fact that such relations can support a
specific form of inference, called analogical inference. This inference
mechanism was empirically proved to be efficient in several reasoning and
classification tasks. In the latter case, it relies on the notion of analogy
preservation.

In this paper, we explore this relation between formal models of analogy and
the corresponding classes of analogy preserving functions, and we establish a
Galois theory of analogical classifiers. We illustrate the usefulness of this
Galois framework over Boolean domains, and we explicitly determine the closed
sets of analogical classifiers, i.e., classifiers that are compatible with the
analogical inference, for each pair of Boolean analogies.

###### Key words and phrases:

Analogical proportion, analogical reasoning, analogical classifier, Galois
theory

##  1\. Introduction and motivation

Analogical reasoning (AR) is a remarkable capability of human thought that
exploits parallels between situations of different nature to infer plausible
conclusions, by relying simultaneously on similarities and dissimilarities.
Machine learning (ML) and artificial intelligence (AI) have tried to develop
AR, mostly based on cognitive considerations, and to integrate it in a variety
of ML tasks, such as natural language processing (NLP), preference learning
and recommendation [2, 18, 19, 34]. Also, analogical extrapolation (inference)
can solve difficult reasoning tasks such as scholastic aptitude tests and
visual question answering [41, 37]. Inference based on AR can also support
dataset augmentation (analogical extension and extrapolation) for model
learning, especially in environments with few labeled examples [15].
Furthermore, AR can also be performed at a meta level for transfer learning
[10, 1] where the idea is to take advantage of what has been learned on a
source domain in order to improve the learning process in a target domain
related to the source domain. Moreover, analogy making can provide useful
explanations that rely on the parallel example-counterexample [23] and guide
counterfactual generation [24].

However, early works lacked theoretical and formalizational support. The
situation started to change about a decade ago when researchers adopted the
view of analogical proportions as statements of the form “$a$ relates to $b$
as $c$ relates to $d$”, usually denoted $a:b::c:d$. Such proportions are at
the root of the analogical inference mechanism, and several formalisms to
study this mechanism have been proposed, which follow different axiomatic and
logical approaches [28, 32]. For instance, Lepage [29] introduces the
following 4 postulates in the linguistic context as a guideline for formal
models of analogical proportions: symmetry (if $a:b::c:d$, then $c:d::a:b$),
central permutation (if $a:b::c:d$, then $a:c::b:d$), strong inner reflexivity
(if $a:a::c:d$, then $d=c$), and strong reflexivity (if $a:b::a:d$, then
$d=b$). Such postulates appear reasonable in the word domain, but they can be
criticized in other application domains. For instance, in a setting where two
distinct conceptual spaces are involved, as in
$\mathit{wine}:\mathit{French}::\mathit{beer}:\mathit{Belgian}$ where two
different spaces “drinks” and “nationality” are considered, the central
permutation is not tolerable.

A key task associated with AR is _analogy solving_ , i.e. finding or
extrapolating, for a given triple $a,b,c$ a value $x$ such that $a:b::c:x$ is
a valid analogy. In fact, this task can be seen as central in case-based
reasoning (CBR) [40]. Given a set $\mathcal{P}$ of problems, a set
$\mathcal{S}$ of solutions and a set $\mathit{CB}$ of problem-solution tuples
$(x,y)\in\mathcal{P}\times\mathcal{S}$, called _cases_ , the CBR task consists
in finding a solution $y_{t}\in\mathcal{S}$ to a given target problem
$x_{t}\in\mathcal{P}$. The CBR methodology splits this problem into several
steps, the two most important being (1) _retrieval:_ select $k$ “relevant”
source cases in the case-base $\mathit{CB}$ according to some criteria related
to the target problem; and (2) _adaptation_ : reuse the $k$ retrieved cases
for proposing a solution to the target problem. The adaptation step obviously
depends on the number of retrieved source cases. For $k=1$, the desired
solution $y_{t}$ corresponds to the solution of the analogical equation
$x:y::x^{t}:y^{t}$. For higher values of $k$, different models of analogy on
$\mathcal{P}$ and $\mathcal{S}$ could be taken into account. For instance,
when $k=3$, the retrieval task consists in finding a triple of cases
$(x^{1},y^{1})$, $(x^{2},y^{2})$ and $(x^{3},y^{3})$, such that
$x^{1}:x^{2}::x^{3}:x^{t}$ is valid and such that $y^{1}:y^{2}::y^{3}:y$ is
solvable in $y$ [30]. In this setting the desired $y^{t}$ would then be one of
such solutions.

The latter idea was extended to analogy based classification [8] where objects
are viewed as attribute tuples (instances) $\mathbf{x}=(x_{1},\ldots,x_{n})$.
Similarly, if $\mathbf{a},\mathbf{b},\mathbf{c}$ are in analogical proportion
for most of their attributes, and class labels are known for
$\mathbf{a},\mathbf{b},\mathbf{c}$ but unknown for $\mathbf{d}$, then one may
infer the label for $\mathbf{d}$ as a solution of an analogical proportion
equation. All these applications rely on the same idea: if four instances
$\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d}$ are in analogical proportion for
most of the attributes describing them, then it may still be the case for the
other attributes $f(\mathbf{a}),f(\mathbf{b}),f(\mathbf{c}),f(\mathbf{d})$
(for some function $f$). This principle is called _analogical inference
principle_ (AIP).

Theoretically, it is quite challenging to find and characterize situations
where AIP can be soundly applied. A first step toward explaining the
analogical mechanism consists in characterizing the set of functions $f$ for
which AIP is sound (i.e., no error occurs) no matter which triplets of
examples are used. In case of Boolean attributes and for the model of
proportional analogy, it was shown in [15] that these so-called “analogy-
preserving” (AP) functions coincide exactly with the set of affine Boolean
functions. Moreover, it was also shown that, when the function is not affine,
the prediction accuracy remains high if the function is close to being affine
[16]. In fact, it was shown that if $f$ is $\varepsilon$-approximately affine
(i.e., $f$ is at Hamming distance at most $\varepsilon$ from the class of
affine functions), then the $f$’s average error rate is at most
$4\varepsilon$. These results were recently extended in [17] to nominal
(finite) underlying sets when taking the minimal model of analogy, i.e., only
patterns of the form $x:x::y:y$ and $x:y::x:y$, in both the domain and
codomain of classifiers.

Intuitively, this class will change when adopting different models of analogy.
In this paper, we investigate the relation between formal models of analogy
and the corresponding class of AP functions. In this paper we establish a
formal correspondence between them describe a Galois theory of analogical
classifiers. Moreover, we revisit Antić’s analogical formalism in the Boolean
case and, for each pair of formal models of analogy, we explicitly determine
the corresponding closed sets of analogical classifiers.

##  2\. Galois theories for functions

Let $A$ and $B$ be nonempty sets. A _function of several arguments_ from $A$
to $B$ is a mapping $f\colon A^{n}\to B$ for some natural number $n$ called
the _arity_ of $f$. Denote by $\mathcal{F}_{AB}^{(n)}$ the set of all $n$-ary
functions of several arguments from $A$ to $B$, and let
$\mathcal{F}_{AB}:=\bigcup_{n\in\mathbb{N}}\mathcal{F}_{AB}^{(n)}$. In the
case when $A=B$ we speak of _operations_ on $A$, and we use the notation
$\mathcal{O}_{A}^{(n)}:=\mathcal{F}_{AA}^{(n)}$ and
$\mathcal{O}_{A}:=\mathcal{F}_{AA}$. For any set $C\subseteq\mathcal{F}_{AB}$,
the _$n$ -ary part_ of $C$ is $C^{(n)}:=C\cap\mathcal{F}_{AB}^{(n)}$.

If $f\in\mathcal{F}_{BC}^{(n)}$ and
$g_{1},\dots,g_{n}\in\mathcal{F}_{AB}^{(m)}$, then the _composition_
$f(g_{1},\dots,g_{n})$ belongs to $\mathcal{F}_{AC}^{(m)}$ and is defined by
the rule

$f(g_{1},\dots,g_{n})(\mathbf{a}):=f(g_{1}(\mathbf{a}),\dots,g_{n}(\mathbf{a}))\quad\text{for
all $\mathbf{a}\in A^{m}$.}$

The $i$-th $n$-ary _projection_
$\mathrm{pr}_{i}^{(n)}\in\mathcal{O}_{A}^{(n)}$ is defined by
$\mathrm{pr}_{i}^{(n)}(a_{1},\dots,a_{n}):=a_{i}$ for all
$a_{1},\dots,a_{n}\in A$. We denote by $\mathcal{J}_{A}$ the set of all
projections on $A$.

The notion of functional composition can be extended to sets of functions as
follows. Let $C\subseteq\mathcal{F}_{BC}$ and $K\subseteq\mathcal{F}_{AB}$.
The _composition_ of $C$ with $K$ is the set

$CK:=\\\ \\{h\in\mathcal{F}_{AC}\mid\exists m,n\in\mathbb{N},\,f\in
C^{(n)},\,g_{1},\dots,g_{n}\in K^{(m)},\,h=f(g_{1},\dots,g_{n})\\}.$

A _clone_ on $A$ is a set $C\subseteq\mathcal{O}_{A}$ that is closed under
composition and contains all projections, in symbols, $CC\subseteq C$ and
$\mathcal{J}_{A}\subseteq C$. For $F\subseteq\mathcal{O}_{A}$, we denote by
$\langle{F}\rangle$ the clone generated by $F$, i.e., the smallest clone on
$A$ containing $F$.

Let $f\in\mathcal{F}_{AB}^{(n)}$ and $g\in\mathcal{F}_{AB}^{(m)}$. We say that
$f$ is a _minor_ of $g$, and we write $f\leq g$, if
$f\in\\{g\\}\mathcal{J}_{A}$, or, equivalently, there exists a
$\sigma\colon\\{1,\dots,m\\}\to\\{1,\dots,n\\}$ such that

$f(a_{1},\dots,a_{n})=g(a_{\sigma(1)},\dots,a_{\sigma(m)})\quad\text{for all
$a_{1},\dots,a_{n}\in A$.}$

The minor relation $\leq$ is a quasi-order (a reflexive and transitive
relation) on $\mathcal{F}_{AB}$. Downsets of $(\mathcal{F}_{AB},{\leq})$ are
called _minor-closed_ classes or _minions._ Equivalently, a set
$C\subseteq\mathcal{F}_{AB}$ is a minion if $C\mathcal{J}_{A}\subseteq C$.

A set $\mathcal{C}\subseteq\mathcal{F}_{AB}$ is _$m$ -locally closed_ if for
all $f\in\mathcal{F}_{AB}$ (say $f$ is $n$-ary), it holds that $f\in C$
whenever for every finite subset $S\subseteq A^{n}$ of size at most $m$, there
exists a $g\in\mathcal{C}$ such that $f|_{S}=g|_{S}$. A set $\mathcal{C}$ is
said to be _locally closed_ if it is $m$-locally closed for every positive
integer $m$.

Subsets of $A^{m}$ are called $m$-ary _relations_ on $A$. Denote by
$\mathcal{R}_{A}^{(m)}$ the set of all $m$-ary relations on $A$, and let
$\mathcal{R}_{A}:=\bigcup_{m\in\mathbb{N}}\mathcal{R}_{A}^{(m)}$. Let
$f\in\mathcal{O}_{A}^{(n)}$ and $R\in\mathcal{R}_{A}^{(m)}$. We say that the
function $f$ _preserves_ the relation $R$ (or $f$ is a _polymorphism_ of $R$,
or $R$ is an _invariant_ of $f$), and we write $f\mathrel{\triangleright}R$,
if for all $\mathbf{a}_{1},\dots,\mathbf{a}_{n}\in R$, we have
$f(\mathbf{a}_{1},\dots,\mathbf{a}_{n})\in R$. Here
$f(\mathbf{a}_{1},\dots,\mathbf{a}_{n})$ means the componentwise application
of $f$ to the tuples, i.e., if $\mathbf{a}_{i}=(a_{i1},\dots,a_{im})$ for
$i\in\\{1,\dots,n\\}$, then

$f(\mathbf{a}_{1},\dots,\mathbf{a}_{n}):=(f(a_{11},\dots,a_{n1}),\dots,f(a_{1m},\dots,a_{nm})).$

The preservation relation $\mathrel{\triangleright}$ induces a Galois
connection between the sets $\mathcal{O}_{A}$ and $\mathcal{R}_{A}$ of
operations and relations on $A$. Its polarities are the maps
$\operatorname{Pol}\colon\mathcal{P}(\mathcal{R}_{A})\to\mathcal{P}(\mathcal{O}_{A})$
and
$\operatorname{Inv}\colon\mathcal{P}(\mathcal{O}_{A})\to\mathcal{P}(\mathcal{R}_{A})$
given by the following rules: for all $\mathcal{R}\subseteq\mathcal{R}_{A}$
and $\mathcal{F}\subseteq\mathcal{O}_{A}$,

$\displaystyle\operatorname{Pol}\mathcal{R}$
$\displaystyle:=\\{f\in\mathcal{O}_{A}\mid\forall R\in\mathcal{R}\colon
f\mathrel{\triangleright}R\\},$ $\displaystyle\operatorname{Inv}\mathcal{F}$
$\displaystyle:=\\{R\in\mathcal{R}_{A}\mid\forall f\in\mathcal{F}\colon
f\mathrel{\triangleright}R\\}.$

Under this Galois connection, the closed sets of operations are precisely the
locally closed clones. The closed sets of relations, known as _relational
clones,_ are precisely the locally closed sets of relations that contain the
empty relation and the diagonal relations and are closed under formation of
primitively positively definable relations. This was first shown for finite
base sets by Bodnarchuk, Kaluzhnin, Kotov, Romov [6, 7] and Geiger [21] and
later extended for arbitrary sets by Szabó [43] and Pöschel [39].

The preservation relation can be adapted for functions of several arguments
from $A$ to $B$; we now need to consider pairs of relations. Let

$\mathcal{R}_{AB}^{(m)}:=\mathcal{R}_{A}^{(m)}\times\mathcal{R}_{B}^{(m)}\quad\text{
and}\quad\mathcal{R}_{AB}:=\bigcup_{m\in\mathbb{N}}\mathcal{R}_{AB}^{(m)}$

be the set of all ($m$-ary) _relational constraints_ from $A$ to $B$.

Let $f\in\mathcal{F}_{AB}^{(n)}$ and $(R,S)\in\mathcal{R}_{AB}^{(m)}$. We say
that $f$ _preserves_ $(R,S)$ (or $f$ is a _polymorphism_ of $(R,S)$, or
$(R,S)$ is an _invariant_ of $f$), and we write
$f\mathrel{\triangleright}(R,S)$, if for all
$\mathbf{a}_{1},\dots,\mathbf{a}_{n}\in R$, we have
$f(\mathbf{a}_{1},\dots,\mathbf{a}_{n})\in S$. As before, the preservation
relation $\mathrel{\triangleright}$ induces a Galois connection between the
sets $\mathcal{F}_{AB}$ and $\mathcal{R}_{AB}$ of functions and relational
constraints from $A$ to $B$. Its polarities are the maps
$\operatorname{Pol}\colon\mathcal{P}(\mathcal{R}_{AB})\to\mathcal{P}(\mathcal{F}_{AB})$
and
$\operatorname{Inv}\colon\mathcal{P}(\mathcal{F}_{AB})\to\mathcal{P}(\mathcal{R}_{AB})$
given by the following rules: for all $\mathcal{Q}\subseteq\mathcal{R}_{AB}$
and $\mathcal{F}\subseteq\mathcal{F}_{AB}$,

$\displaystyle\operatorname{Pol}\mathcal{Q}$
$\displaystyle:=\\{f\in\mathcal{F}_{AB}\mid\forall(R,S)\in\mathcal{Q}\colon
f\mathrel{\triangleright}(R,S)\\},$
$\displaystyle\operatorname{Inv}\mathcal{F}$
$\displaystyle:=\\{(R,S)\in\mathcal{R}_{AB}\mid\forall f\in\mathcal{F}\colon
f\mathrel{\triangleright}(R,S)\\}.$

The sets $\operatorname{Pol}\mathcal{Q}$ and $\operatorname{Inv}\mathcal{F}$
are said to be _defined_ by $\mathcal{Q}$ and $\mathcal{F}$, respectively.
Sets of functions of the form $\operatorname{Pol}\mathcal{Q}$ for some
$\mathcal{Q}\subseteq\mathcal{R}_{AB}$ and sets of relational constraints of
the form $\operatorname{Inv}\mathcal{F}$ for some
$\mathcal{F}\subseteq\mathcal{F}_{AB}$ are said to be _definable_ by
relational constraints and functions, respectively.

The closed sets of functions under this Galois connection were described for
finite base sets by Pippenger [38] and later for arbitrary sets by Couceiro
and Foldes [13]. This result was refined by Couceiro [11] for sets of
functions definable by relations of restricted arity.

######  Theorem 1 ([13, 11]).

Let $A$ and $B$ be arbitrary nonempty sets, and let
$C\subseteq\mathcal{F}_{AB}$.

  1. (i)

$C$ is definable by constraints if and only if $C$ is a locally closed minion.

  2. (ii)

$C$ is definable by constraints of arity $m$ if and only if $C$ is an
$m$-locally closed minion.

The closed sets of relational constraints were described in terms of closure
conditions that parallel those for relational clones.

The description of the dual objects of constraints on possibly infinite sets
$A$ and $B$ was also provided in [13] and inspired by those given by Geiger
[21, 43, 39, 38] and given in terms of positive primitive first-order
relational definitions applied simultaneously on antecedents and consequents.
Sets of constraints that are closed under such formation schemes are said to
be closed under conjunctive minors. Moreover, every function satisfies the
empty $(\varnothing,\varnothing)$ and the equality $(=_{A},=_{B})$
constraints, and if a function $f$ satisfies a constraint $(R,S)$, then $f$
also satisfies its relaxations $(R^{\prime},S^{\prime})$ such that
$R^{\prime}\subseteq R$ and $S^{\prime}\supseteq S$.

As for functions, in the infinite case, we also need to consider a “local
closure” condition to describe the dual closed sets of relational constraints
on $A$ and $B$. A set $\mathcal{Q}$ of constraints on $A$ and $B$ is
$n$-_locally closed_ if it contains every relaxation of its members whose
antecedent has size at most $n$, and it is _locally closed_ if it is
$n$-locally closed for every positive integer $n$.

######  Theorem 2 ([13, 11]).

For arbitrary nonempty sets $A$ and $B$, and let
$\mathcal{Q}\subseteq\mathcal{R}_{AB}$ be a set of relational constraints on
$A$ and $B$.

  1. (i)

$\mathcal{Q}$ is definable by some set $\mathcal{C}\subseteq\mathcal{F}_{AB}$
if and only if it is locally closed, contains the binary equality and the
empty constraints, and it is closed under relaxations and conjunctive minors.

  2. (ii)

$\mathcal{Q}$ is definable by some set
$\mathcal{C}\subseteq\mathcal{F}_{AB}^{(n)}$ of $n$-ary functions if and only
it is $n$-locally closed, contains the binary equality and the empty
constraints, and it is closed under relaxations and conjunctive minors.

Let $K\subseteq\mathcal{F}_{AB}$ and let $C_{1}$ and $C_{2}$ be clones on $A$
and $B$. We say that $K$ is _stable under right composition with $C_{1}$_ if
$KC_{1}\subseteq K$, and we say that $K$ is _stable under left composition
with $C_{2}$_ if $C_{2}K\subseteq K$. We say that $K$ is _$(C_{1},C_{2})$
-stable_ or a _$(C_{1},C_{2})$ -clonoid,_ if $KC_{1}\subseteq K$ and
$C_{2}K\subseteq K$.

Motivated by earlier results on linear definability of equational classes of
Boolean functions [12] which were described in terms of stability under
compositions with the clone of constant preserving affine functions, Couceiro
and Foldes [14] introduced a Galois framework for describing sets of functions
$\mathcal{F}\subseteq\mathcal{F}_{AB}$ stable under right and left
compositions with clones $C_{1}$ on $A$ and $C_{2}$ on $B$, respectively.

For that they restricted the defining dual objects to relational constraints
$(R,S)$ where $R$ and $S$ invariant under $C_{1}$ and $C_{2}$, respectively,
i.e., $R\in\operatorname{Inv}C_{1}$ and $S\in\operatorname{Inv}C_{2}$. These
were referred to as _$(C_{1},C_{2})$ -constraints_. We denote by
$\mathcal{R}_{AB}^{(C_{1},C_{2})}$ the set of all $(C_{1},C_{2})$-constraints.

######  Theorem 3 ([14]).

Let $A$ and $B$ be arbitrary nonempty sets, and let $C_{1}$ and $C_{2}$ clones
on $A$ and $B$, respectively. A set $\mathcal{C}\subseteq\mathcal{F}_{AB}$ is
definable by some set of $(C_{1},C_{2})$-constraints if and only if
$\mathcal{C}$ is locally closed and stable under right and left composition
with $C_{1}$ and $C_{2}$, respectively, i.e., it is a locally closed
$(C_{1},C_{2})$-clonoid.

Dually, a set $\mathcal{Q}$ of $(C_{1},C_{2})$-constraints is definable by a
set $\mathcal{C}\subseteq\mathcal{F}_{AB}$ if
$\mathcal{Q}=\operatorname{Inv}\mathcal{C}\cap\mathcal{R}_{AB}^{(C_{1},C_{2})}$.

To describe the dual closed sets of $(C_{1},C_{2})$-constraints, Couceiro et
al. [14] observed that conjunctive minors of $(C_{1},C_{2})$-constraints are
themselves $(C_{1},C_{2})$-constraints. However, this is not the case for
relaxations. They thus proposed the following variants of local closure and of
constraint relaxations.

A set $\mathcal{Q}_{0}$ of $(C_{1},C_{2})$-constraints is said to be
_$(C_{1},C_{2})$ -locally closed_ if the set $\mathcal{Q}$ of all relaxations
of the various constraints in $\mathcal{Q}_{0}$ is locally closed. A
relaxation $(R_{0},S_{0})$ of a relational constraint $(R,S)$ is said to be a
_$(C_{1},C_{2})$ -relaxation_ if $(R_{0},S_{0})$ is a
$(C_{1},C_{2})$-constraint.

######  Theorem 4 ([14]).

Let $A$ and $B$ be arbitrary nonempty sets, and let $C_{1}$ and $C_{2}$ clones
on $A$ and $B$, respectively. A set $\mathcal{Q}$ of
$(C_{1},C_{2})$-constraints is definable by some set
$\mathcal{C}\subseteq\mathcal{F}_{AB}$ if and only if it is
$(C_{1},C_{2})$-locally closed and contains the binary equality constraint,
the empty constraint, and it is closed under $(C_{1},C_{2})$-relaxations and
conjunctive minors.

In this paper, we will focus on relational constraints whose antecedent and
consequent are derived from analogies, and that we will refer to as
_analogical constraints_. We will denote the set of all analogical constraints
from $A$ to $B$ by $\mathcal{A}_{AB}$.

##  3\. Formal models of analogy

In this section we briefly survey different axiomatic settings to formally
define analogies and different approaches to address the two main problems
dealing with AR, namely, analogy making and solving.

Multiple attempts have been made to formalize and manipulate analogies,
starting as early as De Saussure’s work in 1916 but there is not a consensual
view on the topic. Many works rely on the common view of analogy as a
geometric proportion ($a\times d=b\times c$) or as an arithmetic proportion
($b-a=d-c$), which can be thought of as a parallelogram rule in a vector
space. This view led to an axiomatic approach [28] in which analogies are
quaternary relations satisfying $3$ postulates: reflexivity, symmetry, and
central permutation. These postulates imply many other properties: identity
($a:a::b:b$), internal reversal (if $a:b::c:d$, then $b:a::d:c$), extreme
permutation (if $a:b::c:d$, then $d:b::c:a$), etc.

Another frequently accepted postulate is uniqueness stating that if there
exists $d$ such that $a:b::c:d$, then $d$ is unique. As argued in [31], the
latter postulate is debatable and the authors illustrate it through linguistic
examples, e.g., $\mathit{wine}:\mathit{French}::\mathit{beer}:x$ as
$\mathit{Belgian}$, $\mathit{Czech}$ and $\mathit{German}$ seem reasonable.
This is further illustrated in [3] through arithmetic examples. Take, for
instance, $20:4::30:x$ that has a clear solution $x=6$. However, $x=9$ is
another solution since $(10\cdot 2):2^{2}::(10\cdot 3):3^{2}$. Independently,
it has also been observed that uniqueness and central permutation are not
compatible in simple analogy models in non-Euclidean domains [36].

The framework [3] assumes that pairs $(a,b)$ and $(c,d)$ are interpreted over
two, possibly different, algebras $\mathbb{A}=(A,F)$ and $\mathbb{B}=(B,F)$
with the same functional signature $L$, and called respectively the source and
target domains. Analogies are then modeled by common rewriting transformations
called justifications of the form $s\rightarrow t$, where both $s$ and $t$ are
$L$-terms in such a way that $a=s^{\mathbb{A}}(\mathbf{e}_{1})$ and
$b=t^{\mathbb{A}}(\mathbf{e}_{1})$, for some
$\mathbf{e}_{1}\in\mathbb{A}^{\mid\mathbf{x}\mid}$, and
$c=s^{\mathbb{B}}(\mathbf{e}_{2})$ and $d=t^{\mathbb{B}}(\mathbf{e}_{2})$, for
some $\mathbf{e}_{2}\in\mathbb{B}^{\mid\mathbf{x}\mid}$. A quadruple
$(a,b,c,d)\in A^{2}\times B^{2}$ is then said to be an analogical proportion,
denoted $a:b::c:d$, if there are no $a^{\prime},b^{\prime}\in A$ and
$c^{\prime},d^{\prime}\in B$ such that

  1. (1)

the set of justifications of $(a,b,c,d^{\prime})$ strictly contains that of
$(a,b,c,d)$,

  2. (2)

the set of justifications of $(b,a,d,c^{\prime})$ strictly contains that of
$(b,a,d,c)$,

  3. (3)

the set of justifications of $(c,d,a,b^{\prime})$ strictly contains that of
$(c,d,a,b)$,

  4. (4)

the set of justifications of $(d,c,b,a^{\prime})$ strictly contains that of
$(d,c,b,a)$.

Given $\mathbb{A}$ and $\mathbb{B}$, the relation comprising all analogical
proportions will be referred to as a _formal model of analogy_ or, simply, as
an _analogy_. Note that every analogy fulfills internal reversal and extreme
permutation.

This framework accommodates many formal models of analogies, including the
factorial view of [42] and the functional view of [5, 35], except that it is
not bound by the central permutation postulate. Such a framework is close to
Gentner’s symbolic model of analogical reasoning [22] based on structure
mapping theory and first implemented in [20]. Both share the view that
analogies are compatible with structure preserving maps. However, the latter
prefers knowledge connected facts to isolated ones, and the former fails to
satisfactorily account for analogies over different conceptual spaces as in
$\mathit{wine}:\mathit{French}::\mathit{beer}:\mathit{Belgian}$.

In this paper, we will focus on the case where the source and target domains
coincide (i.e., $\mathbb{B}=\mathbb{A}$), and we will denote the set of all
analogies (on $A$) by $\mathcal{A}_{A}$, and we may omit the subscript $A$
when it is clear from the context. For an analogy $R\in\mathcal{A}_{A}$ we
will adopt the more specific notation $R(a,b,c,d)$ instead of the usual
notation $a:b::c:d$, since we will be dealing simultaneously with multiple
models of analogy.

######  Example 5.

Antić [4] has identified the following 5 relations as the formal models of
analogies on the two-element set $\\{0,1\\}$. Klein’s [25] definition of
Boolean proportion corresponds to $R_{5}$, while Miclet and Prade’s [33]
definition corresponds to $R_{4}$. Here and later, we represent a relation as
a matrix whose columns are precisely the tuples belonging to the relation.

$\displaystyle R_{1}$
$\displaystyle:=\setcounter{MaxMatrixCols}{12}\begin{pmatrix}0&1&0&1&1&0&1&0&0&1&0&1\\\
0&0&1&1&0&1&0&1&0&0&1&1\\\ 0&0&0&0&1&1&0&0&1&1&1&1\\\
0&0&0&0&0&0&1&1&1&1&1&1\end{pmatrix}$ $\displaystyle R_{2}$
$\displaystyle:=\begin{pmatrix}0&1&0&1&1&0&0&1\\\ 0&0&1&1&0&1&0&1\\\
0&0&0&0&1&0&1&1\\\ 0&0&0&0&0&1&1&1\end{pmatrix}$ $\displaystyle R_{3}$
$\displaystyle:=\begin{pmatrix}0&1&1&0&0&1&0&1\\\ 0&1&0&1&0&0&1&1\\\
0&0&1&0&1&1&1&1\\\ 0&0&0&1&1&1&1&1\end{pmatrix}$ $\displaystyle R_{4}$
$\displaystyle:=\begin{pmatrix}0&1&1&0&0&1\\\ 0&1&0&1&0&1\\\ 0&0&1&0&1&1\\\
0&0&0&1&1&1\end{pmatrix}$ $\displaystyle R_{5}$
$\displaystyle:=\begin{pmatrix}0&1&1&0&1&0&0&1\\\ 0&1&0&1&0&1&0&1\\\
0&0&1&1&0&0&1&1\\\ 0&0&0&0&1&1&1&1\end{pmatrix}$

##  4\. Galois theory for analogical classifiers

As mentioned in the Introduction, analogical inference yields competitive
results in classification and recommendation tasks. However, the justification
of why and when a classifier is compatible with the analogical inference
principle (AIP) remained rather obscure until the work of Couceiro et al.
[15]. In this paper the authors considered the minimal Boolean analogy model
(see $R_{4}$ in Example 5) and addressed the problem of determining those
Boolean classifiers for which the AIP always holds, that is, for which there
are no classification errors. Surprisingly, they showed that they correspond
to “analogy preserving” (see Definition 6 below) and that they constitute the
clone of affine functions. This result was later generalized to binary
classification tasks on nominal (finite) domains in [17] where the authors
considered the more stringent notion of “hard analogy preservation”. By taking
the same minimal analogy model made only of analogical proportions of the form
$a:a::b:b$ and $a:b::a:b$ on both the domain and the label set, the authors
showed that in this case the sets of hard analogy preserving functions
constitute Burle’s clones [9].

These preliminary results ask for a better understanding of these analogical
classifiers, and in this paper we seek a general theory of analogical
classifiers that is not dependent on the underlying sets nor on particular
models of analogy. More precisely, we generalize the existing literature by
establishing a Galois theory of analogical classifiers which we then use to
explicitly describe the sets of Boolean analogical classifiers with respect to
the pairs $(R,S)$ of the known Boolean models $R$ and $S$ of analogy. We first
recall the notion of analogy preservation and establish some useful results
that allow us to use the universal algebraic toolbox.

######  Definition 6.

Let $A$ and $B$ be sets, and let $R$ and $S$ be analogical proportions defined
on the two sets, respectively. A function $f\colon A^{n}\to B$ is _analogy-
preserving_ (AP for short) relative to $(R,S)$ if for all
$\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d}\in A^{n}$, the following
implication holds:

$\bigl{(}R(\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d})\quad\text{and}\quad{S}\text{-}\mathrm{solv}(f(\mathbf{a}),f(\mathbf{b}),f(\mathbf{c}))\bigr{)}\implies
S(f(\mathbf{a}),f(\mathbf{b}),f(\mathbf{c}),f(\mathbf{d})),$

where $R(\mathbf{a},\mathbf{b},\mathbf{c},\mathbf{d})$ is a shorthand for
$(a_{i},b_{i},c_{i},d_{i})\in R$ for all $i\in\\{1,\dots,n\\}$ and
${S}\text{-}\mathrm{solv}(f(\mathbf{a}),f(\mathbf{b}),f(\mathbf{c}))$ means
that there is an $x\in B$ with
$S(f(\mathbf{a}),f(\mathbf{b}),f(\mathbf{c}),x)$. Denote by $\mathsf{AP}(R,S)$
the set of all analogy-preserving functions relative to $(R,S)$.

This relation between functions and formal models of analogy gives rise to a
Galois connection whose closed sets of functions correspond exactly to the
classes of analogical classifiers that we now describe.

We start by stating and proving some useful results.

######  Proposition 7.

Let $R$ and $S$ be analogical proportions defined on sets $A$ and $B$,
respectively. Then $\mathsf{AP}(R,S)=\operatorname{Pol}(R,S^{\prime})$, where

(1) $S^{\prime}:=S\cup\\{(a,b,c,d)\in B^{4}\mid\nexists x\in
B\colon(a,b,c,x)\in S\\}.$

###### Proof.

The condition of Definition 6 can be written equivalently as follows: for all
$\mathbf{a}_{1},\dots,\mathbf{a}_{n}\in R$,
$f(\mathbf{a}_{1},\dots,\mathbf{a}_{n})\in S^{\prime}$. This is exactly what
it means that $f$ preserves $(R,S^{\prime})$. Therefore,
$\mathsf{AP}(R,S)=\operatorname{Pol}(R,S^{\prime})$. ∎

######  Example 8.

In continuation to Example 5, the derived relations as in Proposition 7
corresponding to Antić’s analogical proportions on $\\{0,1\\}$ are the
following:

$\displaystyle R^{\prime}_{1}=R_{1},\quad
R^{\prime}_{2}=R_{2}\cup\begin{pmatrix}0&0\\\ 1&1\\\ 1&1\\\
0&1\end{pmatrix},\quad R^{\prime}_{3}=R_{3}\cup\begin{pmatrix}1&1\\\ 0&0\\\
0&0\\\ 0&1\end{pmatrix},$ $\displaystyle
R^{\prime}_{4}=R_{4}\cup\begin{pmatrix}0&0&1&1\\\ 1&1&0&0\\\ 1&1&0&0\\\
0&1&0&1\end{pmatrix},\quad R^{\prime}_{5}=R_{5}.$

To fully describe the sets of the form $\operatorname{Pol}(R,S^{\prime})$ we
need to introduce some variants of the closure conditions discussed in Section
2

Let $\mathcal{R}$ be set of $m$-ary relations on $A$. An $m\times n$ matrix
$D$ whose columns belong to a relation $R\in\mathcal{R}$, is called an
_$\mathcal{R}$ -locality_. Let $\mathcal{Q}\subseteq\mathcal{R}_{AB}$, and let
$\mathcal{Q}_{1}:=\\{R\in\mathcal{R}_{A}\mid\exists S\in\mathcal{R}_{B}\text{
such that }(R,S)\in\mathcal{Q}\\}$. A set
$\mathcal{C}\subseteq\mathcal{F}_{AB}$ is _ $Q$-locally closed_ if for all
$f\in\mathcal{F}_{AB}$ (say $f$ is $n$-ary), it holds that $f\in C$ whenever
for every $\mathcal{Q}_{1}$-locality $D$, either

  1. (1)

there exists a $g\in\mathcal{C}$ such that $fD=gD$, or

  2. (2)

for any relation $R$ in $\mathcal{Q}_{1}$ such that $D\preceq R$ and for any

$T\in\\{S\in\mathcal{R}_{B}\mid(R,S)\in\mathcal{Q},\,\mathcal{C}R\subseteq
S\\}$

we have that $fR\subseteq T$.

Let $\mathcal{A}^{\prime}_{B}:=\\{S^{\prime}\mid S\in\mathcal{A}_{B}\\}$, and
let $\mathcal{A}_{AB}:=\mathcal{A}_{A}\times\mathcal{A}^{\prime}_{B}$. We
refer to the elements of $\mathcal{A}_{AB}$ as _analogical constraints_ from
$A$ to $B$. The set of analogical constraints that are
$(C_{1},C_{2})$-constraints will be denoted by

$\mathcal{A}_{AB}^{(C_{1},C_{2})}:=\mathcal{A}_{AB}\cap\mathcal{R}_{AB}^{(C_{1},C_{2})}.$

A set $\mathcal{C}$ is said to be _$(C_{1},C_{2})$ -analogically locally
closed_ if it is $\mathcal{A}_{AB}^{(C_{1},C_{2})}$-locally closed. Note that
$\mathcal{A}_{AB}=\mathcal{A}_{AB}^{(\mathcal{J}_{A},\mathcal{J}_{B})}$, and
in this case we simply say that $\mathcal{C}$ is _analogically locally
closed._

######  Theorem 9.

Let $A$ and $B$ be arbitrary nonempty sets, and let $C_{1}$ and $C_{2}$ be
clones on $A$ and $B$, respectively.

  1. (1)

A set $\mathcal{C}\subseteq\mathcal{F}_{AB}$ is definable by analogical
$(C_{1},C_{2})$-constraints if and only if it is a
$(C_{1},C_{2})$-analogically locally closed $(C_{1},C_{2})$-clonoid.

  2. (2)

A set $\mathcal{C}\subseteq\mathcal{F}_{AB}$ is definable by analogical
constraints if and only if it is an analogically locally closed minion.

###### Proof.

Note that the second statement is a particular case of the first: just take
$C_{1}$ and $C_{2}$ to be the clones of projections on $A$ and $B$,
respectively. We will thus prove the first statement.

To prove that the conditions are necessary, observe that $\mathcal{C}$ is a
$(C_{1},C_{2})$-clonoid by Theorem 3. It thus remains to show that it is
$(C_{1},C_{2})$-analogically locally closed. Let $f\not\in\mathcal{C}$, say of
arity $n$. Hence, there is an analogical $(C_{1},C_{2})$-constraint
$(R,S)\in\mathcal{A}_{AB}^{(C_{1},C_{2})}$ that is satisfied by every function
in $g\in\mathcal{C}$, but not by $f$. Let
$\mathbf{a}_{1},\dots,\mathbf{a}_{n}\in R$ such that
$f(\mathbf{a}_{1},\dots,\mathbf{a}_{n})\not\in S$. Consider the
$(\mathcal{A}_{AB}^{(C_{1},C_{2})})_{1}$-locality
$D=(\mathbf{a}_{1},\dots,\mathbf{a}_{n})$. As every $g\in\mathcal{C}^{(n)}$
satisfies the constraint $(R,S)$, we have that $fD\neq gD$. Also, $D\preceq
R\in(\mathcal{A}_{AB}^{(C_{1},C_{2})})_{1}$ and it is clear that
$S\in\\{S_{0}\in\mathcal{R}_{B}\mid(R,S_{0})\in\mathcal{A}_{AB}^{(C_{1},C_{2})},\,\mathcal{C}R\subseteq
S_{0}\\}$, and we have $fR\not\subseteq S$ since $fD\not\in S$.

To prove that the conditions are sufficient, we follow a similar strategy to
that in [14] and show that for every $n$-ary $f\not\in\mathcal{C}$, there is
an analogical $(C_{1},C_{2})$-constraint
$(R,S)\in\mathcal{A}_{AB}^{(C_{1},C_{2})}$ that is satisfied by every function
$g\in\mathcal{C}$, but not by $f$. The set of such analogical
$(C_{1},C_{2})$-constraints will then define $\mathcal{C}$.

So suppose that $f\not\in\mathcal{C}$. Since $\mathcal{C}$ is
$(C_{1},C_{2})$-analogically locally closed, there is a
$(\mathcal{A}_{AB}^{(C_{1},C_{2})})_{1}$-locality $D$ such that $fD\neq gD$,
for every $n$-ary $g\in\mathcal{C}$, and there exist
$R\in(\mathcal{A}_{AB}^{(C_{1},C_{2})})_{1}$ with $D\preceq R$, and
$S\in\\{S_{0}\in\mathcal{R}_{B}\mid(R,S_{0})\in\mathcal{A}_{AB}^{(C_{1},C_{2})},\,\mathcal{C}R\subseteq
S_{0}\\}$ such that $fR\not\in S$.

Since $(R,S)$ is an analogical $(C_{1},C_{2})$-constraint that is satisfied by
every function $g\in\mathcal{C}$ (as $\mathcal{C}R\subseteq T$) but not by
$f$, this constitutes the desired constraint separating $f$ and $\mathcal{C}$,
and the proof is thus complete. ∎

Dually, a set $\mathcal{Q}$ of analogical $(C_{1},C_{2})$-constraints is
definable by a set $\mathcal{C}\subseteq\mathcal{F}_{AB}$ if
$\mathcal{Q}=\operatorname{Inv}\mathcal{C}\cap\mathcal{A}_{AB}^{(C_{1},C_{2})}$.
The description of the dual closed sets of analogical constraints is then an
immediate consequence of Theorem 4.

######  Theorem 10.

Let $A$ and $B$ be arbitrary nonempty sets, and let $C_{1}$ and $C_{2}$ be
clones on $A$ and $B$, respectively.

  1. (1)

A set $\mathcal{Q}$ of analogical $(C_{1},C_{2})$-constraints is definable by
some set $\mathcal{C}\subseteq\mathcal{F}_{AB}$ if and only if there exists a
set $\mathcal{Q}_{0}$ of constraints from $A$ to $B$ that is
$(C_{1},C_{2})$-locally closed and contains the binary equality and the empty
constraints, and it is closed under $(C_{1},C_{2})$-relaxations and
conjunctive minors, such that
$\mathcal{Q}=\mathcal{A}_{AB}\cap\mathcal{Q}_{0}$.

  2. (2)

A set $\mathcal{Q}$ of analogical constraints from $A$ to $B$ is definable by
some set $\mathcal{C}\subseteq\mathcal{F}_{AB}$ if and only if there exists a
set $\mathcal{Q}_{0}$ of constraints from $A$ to $B$ that is locally closed
and contains the binary equality and the empty constraints, and it is closed
under relaxations and conjunctive minors, such that
$\mathcal{Q}=\mathcal{A}_{AB}\cap\mathcal{Q}_{0}$.

##  5\. Explicit description of Boolean analogical classifiers

$\mathsf{AP}(R,S)$ | $S$
---|---
$R_{1}$ | $R_{2}$ | $R_{3}$ | $R_{4}$ | $R_{5}$
$R$ | $R_{1}$ | $\mathsf{\Omega(1)}$ | $\mathsf{C}$ | $\mathsf{C}$ | $\mathsf{C}$ | $\mathsf{C}$
$R_{2}$ | $\mathsf{\Omega(1)}$ | $\mathsf{I}$ | $\mathsf{N}$ | $\mathsf{C}$ | $\mathsf{C}$
$R_{3}$ | $\mathsf{\Omega(1)}$ | $\mathsf{N}$ | $\mathsf{I}$ | $\mathsf{C}$ | $\mathsf{C}$
$R_{4}$ | $\mathsf{L}$ | $\mathsf{\Omega(1)}$ | $\mathsf{\Omega(1)}$ | $\mathsf{L}$ | $\mathsf{L}$
$R_{5}$ | $\mathsf{L}$ | $\mathsf{C}$ | $\mathsf{C}$ | $\mathsf{L}$ | $\mathsf{L}$
Table 1. Summary of results. Notation: $\mathsf{L}$ denotes the class of
linear (affine) functions, $\mathsf{\Omega(1)}$ the class of projections,
negations, and constants, $\mathsf{N}$ the class of negations and constants,
$\mathsf{I}$ the class of projections and constants, and $\mathsf{C}$ the
class of constants.

Recall the formal models of analogy $R_{i}$, $i\in[5]$, provided by Antić [4]
on the two-element set $\\{0,1\\}$ (see Example 5). In this section we make
use of the Galois theory described in Section 4 to determine the classes of
analogical classifiers
$\mathsf{AP}(R_{i},R_{j})=\operatorname{Pol}(R_{i},R_{j}^{\prime})$ for all
$i,j\in[{5}]$ (see Example 8 for the relations $R^{\prime}_{j}$ and Equation
(1) for the definition of the extension $S^{\prime}$ of a relation $S$). The
results are summarised in Table 1, together with our notation for various
classes of Boolean functions.

For $a\in\\{0,1\\}$, let $\overline{a}:=1-a,$ and for
$\mathbf{a}=(a_{1},\dots,a_{n})\in\\{0,1\\}^{n}$, let

$\overline{\mathbf{a}}:=(\overline{a_{1}},\dots,\overline{a_{n}}).$

Let $f\colon\\{0,1\\}^{n}\to\\{0,1\\}$. The _( outer) negation_
$\overline{f}$, the _inner negation_ $f^{\mathrm{n}}$, and the _dual_
$f^{\mathrm{d}}$ of $f$ are the $n$-ary Boolean functions given by the rules

$\overline{f}(\mathbf{a}):=\overline{f(\mathbf{a})},\quad
f^{\mathrm{n}}(\mathbf{a}):=f(\overline{\mathbf{a}}),\quad
f^{\mathrm{d}}(\mathbf{a}):=\overline{f(\overline{\mathbf{a}})},\quad\text{for
all $\mathbf{a}\in\\{0,1\\}^{n}$.}$

For $C\subseteq\mathsf{\Omega}$, we let $\overline{C}:=\\{\overline{f}\mid
f\in C\\}$, $C^{\mathrm{n}}:=\\{f^{\mathrm{n}}\mid f\in C\\}$,
$C^{\mathrm{d}}:=\\{f^{\mathrm{d}}\mid f\in C\\}$.

Up to permutation of arguments, the binary Boolean functions are the
following:

  * •

the constant $0$ and $1$ functions, denoted respectively by $0$ and $1$,

  * •

the first projection $\mathrm{pr}_{1}\colon(x_{1},x_{2})\mapsto x_{1}$ and its
negation $\neg_{1}=\overline{\mathrm{pr}_{1}}$,

  * •

the conjunction $\wedge$ and its negation $\uparrow$,

  * •

the disjunction $\vee$ and its negation $\downarrow$,

  * •

the implication $\rightarrow$ and its negation $\nrightarrow$, and

  * •

the addition $+$ modulo 2 and its negation $\leftrightarrow$.

Note that $\uparrow$ and $\downarrow$ are often referred to as Sheffer
functions as each one of them can generate the class of all Boolean functions
by taking compositions and variable substitutions.

The ternary Boolean functions include the triple sum

$\displaystyle\oplus_{3}\colon(x_{1},x_{2},x_{3})\mapsto(x_{1}+x_{2})+x_{3}=x_{1}+(x_{2}+x_{3})$

and its negation $\overline{\oplus_{3}}=\oplus_{3}^{\mathrm{n}}$, and the
median function

$\displaystyle\mu\colon(x_{1},x_{2},x_{3})$ $\displaystyle\mapsto(x_{1}\wedge
x_{2})\vee(x_{1}\wedge x_{3})\vee(x_{2}\wedge x_{3})$
$\displaystyle=(x_{1}\vee x_{2})\wedge(x_{1}\vee x_{3})\wedge(x_{2}\vee
x_{3})$ $\displaystyle=\oplus_{3}(x_{1}\wedge x_{2},x_{1}\wedge
x_{3},x_{2}\wedge x_{3})$

and its negation $\overline{\mu}=\mu^{\mathrm{n}}$.

We also make use of the following terminology. For a relation
$R\subseteq\\{0,1\\}^{m}$, we define its _negation_ $\overline{R}$ by
$\overline{R}:=\\{\overline{\mathbf{a}}\mid\mathbf{a}\in R\\}$.

######  Lemma 11.

$\operatorname{Pol}(R,S)=\operatorname{Pol}(\overline{R},\overline{S})^{\mathrm{d}}$.

###### Proof.

We need to show that $f\mathrel{\triangleright}(R,S)$ if and only if
$f^{\mathrm{d}}\mathrel{\triangleright}(\overline{R},\overline{S})$. Suppose
that $f\mathrel{\triangleright}(R,S)$, and let $M\prec\overline{R}$. Hence,
$\overline{M}\in R$ and we have
$f^{\mathrm{d}}M=f^{\mathrm{d}}\overline{\overline{M}}=\overline{f\overline{M}}\in\overline{S},$
and thus $f^{\mathrm{d}}\mathrel{\triangleright}(\overline{R},\overline{S})$.
The converse implication follows by the same argument. ∎

######  Fact 12.

Let $R$ and $S$ be $m$-ary relations on $\\{0,1\\}$.

  1. (i)

$\mathrm{id}\in\operatorname{Pol}(R,S)$ if and only if $R\subseteq S$.

  2. (ii)

$\neg\in\operatorname{Pol}(R,S)$ if and only if $\overline{R}\subseteq S$.

  3. (iii)

For $a\in\\{0,1\\}$, if $(a,\dots,a)\in S$, then
$a\in\operatorname{Pol}(R,S)$.

Observe that the constant tuples $\mathbf{0}$ and $\mathbf{1}$ belong to every
$R_{i}$ ($i\in[{5}]$), and thus every such $R_{i}$ is invariant under
$\mathsf{I}$, i.e., $\mathsf{I}R_{i}\subseteq R_{i}$. Hence, for every
$i,j\in[{5}]$, $\operatorname{Pol}(R_{i},R^{\prime}_{j})$ is stable under
right composition with $\mathsf{I}$. This leads us to considering the
following notion.

A function $f$ is said to be a $C$-_minor_ of a function $g$ if $f\in gC$.
Recall that in the particular case when $C=\mathcal{J}_{\\{0,1\\}}$, $f$ is
called a minor of $g$. The functions $f$ and $g$ are said to be equivalent,
denoted by $f\equiv g$, if $f$ is a minor of $g$ and $g$ is a minor of $f$.
For further background on these notions and variants see, e.g., [26, 27, 38].

Since $\operatorname{Pol}(R_{i},R^{\prime}_{j})$ is stable under right
composition with $\mathsf{I}$, this means that if an $\mathsf{I}$-minor $f$ of
a function $g$ does not belong to $\operatorname{Pol}(R_{i},R^{\prime}_{j})$,
then neither does $g$. This observation will be used repeatedly in the proofs
of the results that will follow.

######  Lemma 13.

For any $i,j\in[{5}]$, the following statements hold.

  1. (i)

If $\mathrm{id}\notin\operatorname{Pol}(R_{i},R^{\prime}_{j})$ or
$\neg\notin\operatorname{Pol}(R_{i},R^{\prime}_{j})$, then
$\mathord{+},\mathord{\leftrightarrow},\mathord{\rightarrow},\mathord{\nrightarrow}\notin\operatorname{Pol}(R_{i},R^{\prime}_{j})$.

  2. (ii)

If $\mathord{+}\notin\operatorname{Pol}(R_{i},R^{\prime}_{j})$, then
$\mathord{\oplus_{3}}\notin\operatorname{Pol}(R_{i},R^{\prime}_{j})$.

  3. (iii)

If $\mathord{\wedge}\notin\operatorname{Pol}(R_{i},R^{\prime}_{j})$ or
$\mathord{\vee}\notin\operatorname{Pol}(R_{i},R^{\prime}_{j})$, then
$\mu\notin\operatorname{Pol}(R_{i},R^{\prime}_{j})$.

###### Proof.

These results follow immediately from the observation that the sets of the
form $\operatorname{Pol}(R_{i},R^{\prime}_{j})$ are closed under taking
$\mathsf{I}$-minors. The proof is then obtained by verifying that the
functions in the antecedent of the implications are $\mathsf{I}$-minors of
those in the consequent of the implication. We prove this claim by explicitly
for (i), and leave the remaining for the reader.

(i) For every $x\in\\{0,1\\}$,
$\mathrm{id}(x)=\mathord{+}(x,0)=\mathord{\leftrightarrow}(x,1)=\mathord{\rightarrow}(1,x)=\mathord{\nrightarrow}(x,0).$
Similarly, we also have
$\neg(x)=\mathord{+}(x,1)=\mathord{\leftrightarrow}(x,0)=\neg(x)=\mathord{\rightarrow}(x,0)=\mathord{\nrightarrow}(1,x)$.

(ii) and (iii) are shown similarly. ∎

######  Lemma 14.

For any $i,j\in[{5}]$, if
$\mathrm{id},\neg\notin\operatorname{Pol}(R_{i},R^{\prime}_{j})$, then
$\operatorname{Pol}(R_{i},R^{\prime}_{j})=\mathsf{C}$.

###### Proof.

Just note that the only functions that do not have $\mathsf{I}$-minors in
$\\{\mathrm{id},\neg\\}$ are the constant functions. The result thus follows
from the observations above. ∎

######  Proposition 15.

$\mathsf{AP}(R_{1},R_{1})=\operatorname{Pol}(R_{1},R^{\prime}_{1})=\mathsf{\Omega(1)}$.

###### Proof.

Since $R_{1}=R^{\prime}_{1}$, it follows immediately that
$\operatorname{Pol}(R_{1},R^{\prime}_{1})=\operatorname{Pol}R_{1}$ is a clone.

  * •

$0,1,\mathrm{id},\neg\in\operatorname{Pol}(R_{1},R^{\prime}_{1})$ by Fact 12.

  * •

$\mathord{\wedge},\mathord{\vee},\mathord{\oplus_{3}}\notin\operatorname{Pol}(R_{1},R^{\prime}_{1})$
because

$\displaystyle\mathord{\wedge}\begin{pmatrix}1&0\\\ 0&1\\\ 1&1\\\
0&0\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 1\\\ 0\end{pmatrix}\notin
R^{\prime}_{1},$ $\displaystyle\mathord{\vee}\begin{pmatrix}1&0\\\ 0&1\\\
1&1\\\ 0&0\end{pmatrix}=\begin{pmatrix}1\\\ 1\\\ 1\\\ 0\end{pmatrix}\notin
R^{\prime}_{1},$ $\displaystyle\mathord{\oplus_{3}}\begin{pmatrix}1&0&1\\\
0&1&1\\\ 1&1&1\\\ 0&1&1\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 1\\\
0\end{pmatrix}\notin R^{\prime}_{1}.$

  * •

$\mu\notin\operatorname{Pol}(R_{1},R^{\prime}_{1})$ follows by Lemma 13(iii).

It follows that $\operatorname{Pol}R_{1}$ does not contain generators of any
minimal clone with essentially at least binary functions. From this it follows
that
$\operatorname{Pol}(R_{1},R^{\prime}_{1})=\langle{0,1,\neg}\rangle=\mathsf{\Omega(1)}$.
∎

######  Proposition 16.

$\mathsf{AP}(R_{2},R_{2})=\operatorname{Pol}(R_{2},R^{\prime}_{2})=\mathsf{I}$.

###### Proof.

Observe that

  * •

$0,1,\mathrm{id}\in\operatorname{Pol}(R_{2},R^{\prime}_{2})$ by Fact 12.

  * •

$\neg,\mathord{\wedge},\mathord{\vee}\notin\operatorname{Pol}(R_{2},R^{\prime}_{2})$
because

$\displaystyle\neg\begin{pmatrix}0\\\ 1\\\ 0\\\
0\end{pmatrix}=\begin{pmatrix}1\\\ 0\\\ 1\\\ 1\end{pmatrix}\notin
R^{\prime}_{2},$ $\displaystyle\mathord{\wedge}\begin{pmatrix}1&0\\\ 0&0\\\
1&1\\\ 0&1\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 1\\\ 0\end{pmatrix}\notin
R^{\prime}_{2},$ $\displaystyle\mathord{\vee}\begin{pmatrix}1&0\\\ 0&0\\\
1&1\\\ 0&1\end{pmatrix}=\begin{pmatrix}1\\\ 0\\\ 1\\\ 1\end{pmatrix}\notin
R^{\prime}_{2}.$

  * •

$\mathord{\leftrightarrow}\notin\operatorname{Pol}(R_{2},R^{\prime}_{2})$
follows by Lemma 13(i).

The remaining functions that are neither projections nor constants have
$\mathsf{I}$-minors in
$\\{\mathord{\neg},\mathord{\wedge},\mathord{\vee},\mathord{\leftrightarrow}\\}$.
From this it follows that
$\operatorname{Pol}(R_{2},R^{\prime}_{2})=\mathsf{I}$. ∎

######  Proposition 17.

$\mathsf{AP}(R_{3},R_{3})=\operatorname{Pol}(R_{3},R^{\prime}_{3})=\mathsf{I}$.

###### Proof.

Since $R_{3}=\overline{R_{2}}$, $R^{\prime}_{3}=\overline{R^{\prime}_{2}}$,
and $\mathsf{I}^{\mathrm{d}}=\mathsf{I}$, the claim follows from Lemma 11 and
Proposition 16. ∎

######  Proposition 18.

$\mathsf{AP}(R_{5},R_{5})=\operatorname{Pol}(R_{5},R^{\prime}_{5})=\mathsf{L}$.

###### Proof.

Since $R_{5}=R^{\prime}_{5}$, it follows immediately that
$\operatorname{Pol}(R_{5},R^{\prime}_{5})=\operatorname{Pol}R_{5}$ is a clone,
and it is well known that $\operatorname{Pol}R_{5}=\mathsf{L}$. ∎

######  Proposition 19.

$\mathsf{AP}(R_{4},R_{4})=\mathsf{AP}(R_{4},R_{5})=\mathsf{AP}(R_{5},R_{4})=\mathsf{AP}(R_{4},R_{1})=\mathsf{AP}(R_{5},R_{1})=\mathsf{L}$.

###### Proof.

We make use of the fact that
$\mathsf{AP}(R,S)=\operatorname{Pol}(R,S^{\prime})$, and prove the equality
$\mathsf{AP}(R_{4},R_{4})=\operatorname{Pol}(R_{4},R^{\prime}_{4})=\mathsf{L}$.
The equalities
$\operatorname{Pol}(R_{4},R^{\prime}_{5})=\operatorname{Pol}(R_{5},R^{\prime}_{4})=\mathsf{L}$
are established by the same argument.

  * •

Since $(R_{4},R^{\prime}_{4})$ is a relaxation of $(R_{5},R^{\prime}_{5})$,
$\operatorname{Pol}(R_{4},R^{\prime}_{4})\supseteq\operatorname{Pol}(R_{5},R^{\prime}_{5})=\mathsf{L}$
by Proposition 18.

  * •

$\mathord{\wedge},\mathord{\vee}\notin\operatorname{Pol}(R_{4},R^{\prime}_{4})$
because

$\displaystyle\mathord{\wedge}\begin{pmatrix}1&0\\\ 0&0\\\ 1&1\\\
0&1\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 1\\\ 0\end{pmatrix}\notin
R^{\prime}_{4},$ $\displaystyle\mathord{\vee}\begin{pmatrix}1&0\\\ 1&1\\\
0&0\\\ 0&1\end{pmatrix}=\begin{pmatrix}1\\\ 1\\\ 0\\\ 1\end{pmatrix}\notin
R^{\prime}_{4}.$

  * •

$\mathord{\uparrow},\mathord{\downarrow}\notin\operatorname{Pol}(R_{4},R^{\prime}_{4})$
because

$\displaystyle\mathord{\uparrow}\begin{pmatrix}0&1\\\ 0&0\\\ 1&1\\\
1&0\end{pmatrix}=\begin{pmatrix}1\\\ 1\\\ 0\\\ 1\end{pmatrix}\notin
R^{\prime}_{4},$ $\displaystyle\mathord{\downarrow}\begin{pmatrix}0&1\\\
1&1\\\ 0&0\\\ 1&0\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 1\\\
0\end{pmatrix}\notin R^{\prime}_{4}.$

  * •

$\mathord{\nrightarrow},\mathord{\rightarrow}\notin\operatorname{Pol}(R_{4},R^{\prime}_{4})$
because

$\displaystyle\mathord{\nrightarrow}\begin{pmatrix}0&1\\\ 0&0\\\ 1&1\\\
1&0\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 0\\\ 1\end{pmatrix}\notin
R^{\prime}_{4},$ $\displaystyle\mathord{\rightarrow}\begin{pmatrix}0&1\\\
0&0\\\ 1&1\\\ 1&0\end{pmatrix}=\begin{pmatrix}1\\\ 1\\\ 1\\\
0\end{pmatrix}\notin R^{\prime}_{4}.$

The result now follows by observing that any function outside of $\mathsf{L}$
has an $\mathsf{I}$-minor in
$\\{\mathord{\wedge},\mathord{\vee},\mathord{\uparrow},\mathord{\downarrow},\mathord{\nrightarrow},\mathord{\rightarrow}\\}$.
To see that this claim holds, we make use of the well-known fact that every
Boolean function can be represented by a unique multilinear polynomial over
the 2-element field $GF(2)$.

So suppose that $f\not\in\mathsf{L}$, i.e., there is a monomial in the
multilinear representation of $f$ with degree111The degree of a monomial is
the number of variables in it, and the degree of a multilinear polynomial is
the largest degree among its monomials. at least 2. Take a minimal monomial
with at least 2 variables; without loss of generality, suppose that it is
$x_{1}x_{2}x_{3}\cdots x_{j}$ .

Consider the $\mathsf{I}$-minor $f^{\prime}$ of $f$ obtained by:

  * •

substituting $1$ for each $x_{3},\cdots,x_{j}$, and

  * •

substituting $0$ for every other variable in the polynomial representation of
$f$.

It is not difficult to verify that $f^{\prime}=x_{1}x_{2}+ax_{1}+bx_{2}+c$,
for some $a,b,c\in\\{0,1\\}$, and

  * •

$f^{\prime}\equiv\mathord{\wedge}$, if $a=b=c=0$;

  * •

$f^{\prime}\equiv\mathord{\uparrow}$, if $a=b=0$ and $c=1$;

  * •

$f^{\prime}\equiv\mathord{\vee}$, if $a=b=1$ and $c=0$;

  * •

$f^{\prime}\equiv\mathord{\downarrow}$, if $a=b=c=1$;

  * •

$f^{\prime}\equiv\mathord{\nrightarrow}$, if $a=c=1$ and $b=0$, or if $b=c=1$
and $a=0$;

  * •

$f^{\prime}\equiv\mathord{\rightarrow}$, if $a=1$ and $b=c=0$, or if $b=1$ and
$a=c=0$.

This completes the proof of the claim and, hence, of the proposition. ∎

######  Proposition 20.

$\mathsf{AP}(R_{1},R_{2})=\mathsf{AP}(R_{1},R_{3})=\mathsf{C}$.

###### Proof.

We have $0,1\in\operatorname{Pol}(R_{1},R^{\prime}_{2})$ and
$\mathrm{id},\neg\notin\operatorname{Pol}(R_{1},R^{\prime}_{2})$ by Fact 12.
Therefore, $\operatorname{Pol}(R_{1},R^{\prime}_{2})=\mathsf{C}$ follows by
Lemma 14. Since $R_{1}=\overline{R_{1}}$,
$R^{\prime}_{3}=\overline{R^{\prime}_{2}}$, and
$\mathsf{C}^{\mathrm{d}}=\mathsf{C}$, the equality
$\operatorname{Pol}(R_{1},R^{\prime}_{3})=\mathsf{C}$ follows by Lemma 11. ∎

######  Proposition 21.

$\mathsf{AP}(R_{2},R_{1})=\mathsf{AP}(R_{3},R_{1})=\mathsf{\Omega(1)}$.

###### Proof.

We only prove the equality
$\operatorname{Pol}(R_{2},R^{\prime}_{1})=\mathsf{\Omega(1)}$. Since
$R_{3}=\overline{R_{2}}$, $R^{\prime}_{1}=\overline{R^{\prime}_{1}}$, and
$\mathsf{\Omega(1)}^{\mathrm{d}}=\mathsf{\Omega(1)}$, the equality
$\operatorname{Pol}(R_{3},R^{\prime}_{1})=\mathsf{\Omega(1)}$ follows by Lemma
11.

  * •

$0,1,\mathrm{id},\neg\in\operatorname{Pol}(R_{2},R^{\prime}_{1})$ by Fact 12.

  * •

$\mathord{+},\mathord{\nrightarrow},\mathord{\wedge},\mathord{\vee}\notin\operatorname{Pol}(R_{2},R^{\prime}_{1})$
because

$\displaystyle\mathord{+}\begin{pmatrix}1&1\\\ 0&0\\\ 0&1\\\
0&0\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 1\\\ 0\end{pmatrix}\notin
R^{\prime}_{1},$ $\displaystyle\mathord{\nrightarrow}\begin{pmatrix}1&1\\\
0&1\\\ 1&0\\\ 0&0\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 1\\\
0\end{pmatrix}\notin R^{\prime}_{1},$
$\displaystyle\mathord{\wedge}\begin{pmatrix}1&0\\\ 0&0\\\ 1&1\\\
0&1\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 1\\\ 0\end{pmatrix}\notin
R^{\prime}_{1},$ $\displaystyle\mathord{\vee}\begin{pmatrix}1&1\\\ 1&0\\\
0&1\\\ 0&0\end{pmatrix}=\begin{pmatrix}1\\\ 1\\\ 1\\\ 0\end{pmatrix}\notin
R^{\prime}_{1}.$

  * •

Since $R^{\prime}_{1}=\overline{R^{\prime}_{1}}$, it follows immediately from
the above that
$\mathord{\leftrightarrow},\mathord{\rightarrow},\mathord{\uparrow},\mathord{\downarrow}\notin\operatorname{Pol}(R_{2},R^{\prime}_{1})$.

From these observations and using the technique based on $\mathsf{I}$-minors,
it follows that $\operatorname{Pol}(R_{2},R^{\prime}_{1})=\mathsf{\Omega(1)}$.
∎

######  Proposition 22.

$\mathsf{AP}(R_{2},R_{3})=\mathsf{AP}(R_{3},R_{2})=\mathsf{N}$.

###### Proof.

We only prove the equality
$\operatorname{Pol}(R_{2},R^{\prime}_{3})=\mathsf{N}$. Since
$R_{3}=\overline{R_{2}}$, $R^{\prime}_{2}=\overline{R^{\prime}_{3}}$, and
$\mathsf{N}^{\mathrm{d}}=\mathsf{N}$, the equality
$\operatorname{Pol}(R_{3},R^{\prime}_{2})=\mathsf{N}$ follows by Lemma 11.

  * •

$0,1,\neg\in\operatorname{Pol}(R_{2},R^{\prime}_{3})$ and
$\mathrm{id}\notin\operatorname{Pol}(R_{2},R^{\prime}_{3})$ by Fact 12.

  * •

$\mathord{+},\mathord{\leftrightarrow},\mathord{\nrightarrow},\mathord{\rightarrow}\notin\operatorname{Pol}(R_{2},R^{\prime}_{3})$
follows from Lemma 13(i).

Any other function has an $\mathsf{I}$-minor in
$\\{\mathord{+},\mathord{\leftrightarrow},\mathord{\nrightarrow},\mathord{\rightarrow}\\}$.
Thus $\operatorname{Pol}(R_{2},R^{\prime}_{3})=\mathsf{N}$. ∎

######  Proposition 23.

$\mathsf{AP}(R_{4},R_{2})=\mathsf{AP}(R_{4},R_{3})=\mathsf{\Omega(1)}$.

###### Proof.

We only prove the equality
$\operatorname{Pol}(R_{4},R^{\prime}_{2})=\mathsf{\Omega(1)}$. Since
$R_{4}=\overline{R_{4}}$, $R^{\prime}_{3}=\overline{R^{\prime}_{2}}$, and
$(\mathsf{\Omega(1)})^{\mathrm{d}}=\mathsf{\Omega(1)}$, the equality
$\operatorname{Pol}(R_{4},R^{\prime}_{3})=\mathsf{\Omega(1)}$ follows by Lemma
11.

  * •

$0,1,\mathrm{id},\neg\in\operatorname{Pol}(R_{4},R^{\prime}_{2})$ by Fact 12.

  * •

$\mathord{+},\mathord{\leftrightarrow},\mathord{\rightarrow},\mathord{\nrightarrow},\mathord{\wedge},\mathord{\vee},\mathord{\uparrow},\mathord{\downarrow}\notin\operatorname{Pol}(R_{4},R^{\prime}_{2})$
because

$\displaystyle\mathord{+}\begin{pmatrix}1&0\\\ 0&0\\\ 1&1\\\
0&1\end{pmatrix}=\begin{pmatrix}1\\\ 0\\\ 0\\\ 1\end{pmatrix}\notin
R^{\prime}_{2},$ $\displaystyle\mathord{\leftrightarrow}\begin{pmatrix}0&0\\\
1&0\\\ 0&1\\\ 1&1\end{pmatrix}=\begin{pmatrix}1\\\ 0\\\ 0\\\
1\end{pmatrix}\notin R^{\prime}_{2},$
$\displaystyle\mathord{\rightarrow}\begin{pmatrix}0&0\\\ 0&1\\\ 1&0\\\
1&1\end{pmatrix}=\begin{pmatrix}1\\\ 1\\\ 0\\\ 1\end{pmatrix}\notin
R^{\prime}_{2},$ $\displaystyle\mathord{\nrightarrow}\begin{pmatrix}0&0\\\
0&1\\\ 1&0\\\ 1&1\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 1\\\
0\end{pmatrix}\notin R^{\prime}_{2},$
$\displaystyle\mathord{\wedge}\begin{pmatrix}0&0\\\ 0&1\\\ 1&0\\\
1&1\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 0\\\ 1\end{pmatrix}\notin
R^{\prime}_{2},$ $\displaystyle\mathord{\vee}\begin{pmatrix}1&1\\\ 0&1\\\
1&0\\\ 0&0\end{pmatrix}=\begin{pmatrix}1\\\ 1\\\ 1\\\ 0\end{pmatrix}\notin
R^{\prime}_{2},$ $\displaystyle\mathord{\uparrow}\begin{pmatrix}0&0\\\ 0&1\\\
1&0\\\ 1&1\end{pmatrix}=\begin{pmatrix}1\\\ 1\\\ 1\\\ 0\end{pmatrix}\notin
R^{\prime}_{2},$ $\displaystyle\mathord{\downarrow}\begin{pmatrix}1&1\\\
0&1\\\ 1&0\\\ 0&0\end{pmatrix}=\begin{pmatrix}0\\\ 0\\\ 0\\\
1\end{pmatrix}\notin R^{\prime}_{2}.$

Since any other function has an $\mathsf{I}$-minor in
$\\{\mathord{+},\mathord{\leftrightarrow},\mathord{\rightarrow},\mathord{\nrightarrow},\mathord{\wedge},\mathord{\vee},\mathord{\uparrow},\mathord{\downarrow}\\}$,
it follows that $\operatorname{Pol}(R_{2},R^{\prime}_{3})=\mathsf{\Omega(1)}$.
∎

######  Proposition 24.

For any

$(R,S)\in\\{(R_{1},R_{4}),(R_{1},R_{5}),(R_{2},R_{4}),(R_{2},R_{5}),(R_{3},R_{5}),(R_{5},R_{2}),(R_{5},R_{3})\\},$

we have $\mathsf{AP}(R,S)=\mathsf{C}$.

###### Proof.

We have $0,1\in\operatorname{Pol}(R,S)$ and
$\mathrm{id},\neg\notin\mathsf{AP}(R,S)$ by Fact 12, so
$\mathsf{AP}(R,S)=\mathsf{C}$ follows by Lemma 14. ∎

##  6\. Conclusion and perspectives

In this paper we addressed and tackled the question of determining classes of
analogical classifiers. Our approach makes use of model theoretic and
universal algebraic tools that we used to establish a general Galois theory of
such analogical classifiers that does not depend on the underlying domains nor
the formal models of analogy considered. In the particular case of Boolean
analogies, in which several formal models of analogy have been identified, we
made use of this Galois framework to explicitly describe, for each pair of
known analogies, the respective sets of analogical classifiers.

As future work, we intend to further explore different formal models of
analogy that may be obtained by considering different algebraic signatures.
For instance, in [4], Antić only considered reducts of the 2-element Boolean
algebra for which he provided all Boolean analogies. However, other algebraic
signatures and their reducts could be considered, such as that of median
algebras and fields. These may give rise to further models of analogy
considered over different underlying domains, and for which we may obtain
other sets of analogical classifiers. Further related questions of model
theoretic and universal algebraic flavour will also be addressed.

### Acknowledgments

The authors wish to thank Esteban Marquer and Pierre-Alexandre Murena for the
insightful discussions and useful suggestions for improving this manuscript.

This research was partially supported by TAILOR, a project funded by EU
Horizon 2020 research and innovation program under GA No 952215, and the Inria
Project Lab “Hybrid Approaches for Interpretable AI” (HyAIAI).

This work was also partially funded by National Funds through the FCT –
Fundação para a Ciência e a Tecnologia, I.P., under the scope of the project
UIDB/00297/2020 (Center for Mathematics and Applications) and the project
PTDC/MAT-PUR/31174/2017.

## References

  * [1] S. Alsaidi, A. Decker, P. Lay, E. Marquer, P.-A. Murena, and M. Couceiro.  On the transferability of neural models of morphological analogies.  In AIMLAI@ECML/PKDD 2021, pages 76–89.
  * [2] S. Alsaidi, A. Decker, P. Lay, E. Marquer, P.-A. Murena, and M. Couceiro.  A neural approach for detecting morphological analogies.  In IEEE 8th DSAA, pages 1–10, 2021.
  * [3] Ch. Antić.  Analogical proportions, 2020.
  * [4] Ch. Antić.  Boolean proportions, 2021.
  * [5] N. Barbot, L. Miclet, and H. Prade.  Analogy between concepts.  Artif. Intell., 275:487–539, 2019.
  * [6] V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov.  Galois theory for Post algebras I.  Kibernetika, 5(3):1–10, 1969.
  * [7] V. G. Bodnarchuk, L. A. Kaluzhnin, V. N. Kotov, and B. A. Romov.  Galois theory for Post algebras II.  Kibernetika, 5(5):1–9, 1969.
  * [8] M. Bounhas, H. Prade, and G. Richard.  Analogy-based classifiers for nominal or numerical data.  IJAR, 91:36–55, 2017.
  * [9] G. A. Burle.  Classes of $k$-valued logic which contain all functions of a single variable.  Diskret. Analiz, Novosibirsk, 10:3–7, 1967.
  * [10] A. Cornuéjols, P.-A. Murena, and R. Olivier.  Transfer learning by learning projections from target to source.  In IDA 2020, volume 12080 of LNCS, pages 119–131, Springer, 2020.
  * [11] M. Couceiro.  On Galois connections between external operations and relational constraints: arity restrictions and operator decompositions.  Acta Sci. Math., 72(1-2):15–35, 2006.
  * [12] M. Couceiro and S. Foldes.  Definability of Boolean function classes by linear equations over $\mathbf{GF}(2)$.  Discrete Appl. Math., 142(1-3):29–34, 2004.
  * [13] M. Couceiro and S. Foldes.  On closed sets of relational constraints and classes of functions closed under variable substitutions.  Algebra Universalis, 54:149–165, 2005.
  * [14] M. Couceiro and S. Foldes.  Function classes and relational constraints stable under compositions with clones.  Discuss. Math., Gen. Algebra Appl., 29(2):109–121, 2009.
  * [15] M. Couceiro, N. Hug, H. Prade, and G. Richard.  Analogy-preserving functions: A way to extend Boolean samples.  In IJCAI 2017, pages 1575–1581. ijcai.org.
  * [16] M. Couceiro, N. Hug, H. Prade, and G. Richard.  Behavior of analogical inference w.r.t. Boolean functions.  In IJCAI 2018, pages 2057–2063. ijcai.org.
  * [17] M. Couceiro, E. Lehtonen, L. Miclet, H. Prade, and G. Richard.  When nominal analogical proportions do not fail.  In SUM 2020,, volume 12322 of LNCS, pages 68–83, Springer, 2020.
  * [18] M. A. Fahandar and E. Hüllermeier.  Learning to rank based on analogical reasoning.  In AAAI-18, pages 2951–2958, 2018.
  * [19] M. A. Fahandar and E. Hüllermeier.  Analogical embedding for analogy-based learning to rank.  In IDA 2021, volume 12695 of LNCS, pages 76–88, Springer, 2021.
  * [20] B. Falkenhainer, K. D. Forbus, and D. Gentner.  The structure-mapping engine: Algorithm and examples.  Artif. Intell., 41(1):1–63, 1989.
  * [21] D. Geiger.  Closed systems of functions and predicates.  Pacific J. Math., 27:95–100, 1968.
  * [22] D. Gentner and C. Hoyos.  Analogy and abstraction.  Top. Cogn. Sci., 9(3):672–693, 2017.
  * [23] E. Hüllermeier.  Towards analogy-based explanations in machine learning.  In MDAI 2020, volume 12256 of LNCS, pages 205–217, Springer, 2020.
  * [24] M. T. Keane and B. Smyth.  Good counterfactuals and where to find them: A case-based technique for generating counterfactuals for explainable AI (XAI).  In ICCBR 2020, volume 12311 of LNCS, pages 163–178, Springer, 2020.
  * [25] S. Klein.  Culture, mysticism & social structure and the calculation of behavior.  In Proc. 5th Europ. Conf. in Artificial Intelligence (ECAI’82), pages 141–146, 1982.
  * [26] E. Lehtonen.  Descending chains and antichains of the unary, linear, and monotone subfunction relations.  Order, 23:129–142, 2006.
  * [27] E. Lehtonen and Á. Szendrei.  Partial orders induced by quasilinear clones.  In Contributions to General Algebra 20, pages 51–84, Klagenfurt, 2012. Verlag Johannes Heyn.
  * [28] Y. Lepage.  Analogy and formal languages.  Electron. Notes Theor. Comput. Sci., 53:180–191, 2001.
  * [29] Y. Lepage.  De l’analogie rendant compte de la commutation en linguistique.  2003\.
  * [30] J. Lieber, E. Nauer, and H. Prade.  When revision-based case adaptation meets analogical extrapolation.  In ICCBR 2021, volume 12877 of LNCS, pages 156–170, Springer, 2021.
  * [31] S. Lim, H. Prade, and G. Richard.  Classifying and completing word analogies by machine learning.  International Journal of Approximate Reasoning, 132:1–25, 2021\.
  * [32] L. Miclet, S. Bayoudh, and A. Delhay.  Analogical dissimilarity: Definition, algorithms and two experiments in machine learning.  J. Artif. Intell. Res., 32:793–824, 2008.
  * [33] L. Miclet and H. Prade.  Handling analogical proportions in classical logic and fuzzy logics settings.  In G. Chemello C. Sossai, editor, Proc. 10th Europ. Conf. on Symbolic and Quantitative Approaches to Reasoning with Uncertainty (ECSQARU 2009), pages 638–650, Berlin/Heidelberg, 2009. Springer.
  * [34] M. Mitchell.  Abstraction and analogy-making in artificial intelligence, 2021.
  * [35] P.-A. Murena, M. Al-Ghossein, J.-L. Dessalles, and A. Cornuéjols.  Solving analogies on words based on minimal complexity transformation.  In IJCAI, pages 1848–1854, 2020.
  * [36] P.-A. Murena, A. Cornuéjols, and J.-L. Dessalles.  Opening the parallelogram: Considerations on non-Euclidean analogies.  In International Conference on Case-Based Reasoning, pages 597–611. Springer, 2018.
  * [37] J. Peyre, I. Laptev, C. Schmid, and J. Sivic.  Detecting unseen visual relations using analogies.  In IEEE ICCV 2019, pages 1981–1990, 2019.
  * [38] N. Pippenger.  Galois theory for minors of finite functions.  Discrete Math., 254(1-3):405–419, 2002.
  * [39] R. Pöschel.  Concrete representation of algebraic structures and a general Galois theory.  In H. Kautschitsch, W. B. Müller, and W. Nöbauer, editors, Contributions to General Algebra (Proc. Klagenfurt Conf., Klagenfurt, 1978), pages 249–272, Klagenfurt, 1979. Johannes Heyn.
  * [40] M. M. Richter and R. O. Weber.  Case-based reasoning.  Springer, 2016.
  * [41] F. Sadeghi, C. L. Zitnick, and A. Farhadi.  Visalogy: Answering visual analogy questions.  In NIPS 2015, pages 1882–1890, 2015.
  * [42] N. Stroppa and F. Yvon.  An analogical learner for morphological analysis.  In CoNLL 2005, pages 120–127, ACL, 2005.
  * [43] L. Szabó.  Concrete representation of related structures of universal algebras. i.  Acta Sci. Math. (Szeged), 40:175–184, 1978.