\section{Introduction}\label{sec:introduction}

\newcommand{arxiv}{arxiv}

\makeatother

\newcommand{\newatticus}[1]{{\color{red}#1}}
\newcommand{\newmike}[1]{{\color{red}#1}}
\newcommand{\newalex}[1]{{\color{red}#1}}
\newcommand{Methods}{Methods}
\newcommand{our Appendix}{our Appendix}
\newcommand{Appendix}{Appendix}

One of the key components of human intelligence is our ability to reason about abstract relations between stimuli. Many of the most unremarkable human activities -- scheduling a meeting, following traffic signs, assembling furniture -- require a fluency with abstraction and relational reasoning that is unmatched in nonhuman animals. An influential perspective on human uniqueness holds that relational concepts are critical to higher-order cognition \citep[e.g.,][]{gentner:2003}. By far the most common case study of abstract relations has been equality.\footnote{We use the term ``equality'' here, though different literatures have also used ``identity.''} Equality is a valuable case study because it is simple and ubiquitous, but also completely abstract in the sense that it can be evaluated regardless of the identity of the stimuli being judged.

Human equality reasoning has been studied extensively across a host of systems and tasks, with wildly variant conclusions. In some studies, equality is very challenging to learn: only great apes with either extensive language experience or specialized training succeed in matching tasks in which a \emph{same} pair, AA, must be matched to a novel same pair, BB \citep{Premack:1983,thompson:2001}. Preschool children also struggle to learn these regularities in a seemingly similar task \citep{walker:2016}. In contrast, other studies suggest that equality is simple: bees are able to learn abstract identity relationships from only a small set of training trials \citep{giurfa:2001,avargues:2011}, and human infants can generalize identity patterns \citep{anderson:2018} and succeed in relational matching tasks \citep{ferry:2015}. We take the central challenge of this literature to be characterizing the conditions that lead to success or failure in learning an abstract relation in a way that can be productively generalized to new stimuli \citep{carstensen:inpress}.

The learning task in all of these cases can be described using the predicate \emph{same} (or equivalently, =), which operates over two inputs and returns {\sc true} if they are identical in some respect, else {\sc false}. One perspective in the literature is that success in these learning tasks implies the presence of an equivalent symbolic description in the mind of the solver \citep{marcus:1999,Premack:1983}. This view does not provide a lever to distinguish which of these tasks are trivial and which are difficult, however. Further, it can fall prey to circularity: because newborns show sensitivity to identity relations \citep{gervain:2012}, then it would follow from this argument that they must have symbolic representations. If this logic applies also to bees, then we presuppose symbolic representations universally and have no account of the gradient difficulty of different tasks for different species.

An explanation of when same--different tasks are trivial and when they are difficult requires a theoretical framework beyond the symbolic/non-symbolic distinction. To make quantitative predictions about task performance, such a framework should ideally be instantiated in a computational model that takes in training data and learns a solution that generalizes when assessed with stimuli analogous to those used in experimental assessments. Symbolic computational models \citep[e.g.,][]{frank:2011} can be used to make contact with data about the breadth of generalizations that humans make. But such models require the existence of a symbolic equality predicate and hence again presuppose symbolic abilities in every case of success. Ideally, we would want a model that describes under what conditions \emph{same} is easy and under what conditions it is hard or unlearnable -- and how learning proceeds in hard cases. Here, we aim to lay the foundation for the development of such an account.

We are inspired by an emergent perspective in the animal learning literature that the representations underlying non-human animals' and human infants' successes in equality reasoning tasks are graded \citep{wasserman:2017}. This view acknowledges the increasing evidence that other species like pigeons \citep{cook2007}, crows \citep{smirnova2015}, and baboons \citep{fagot2011} can make true, out-of-sample generalizations of \emph{same} and \emph{different} relations, but it also recognizes that the observed patterns of behavior do not show the hallmarks of all-or-none symbolic representations. Instead, performance is graded. Out-of-sample generalization is possible but the level of performance depends critically on the diversity of the training stimuli \citep[e.g.,][]{castro2010}. Success requires hundreds, thousands, or even tens of thousands of training trials. And the outcome of learning is noisy and imperfect. These learning signatures appear to be a close match to the kind of learning exhibited by neural networks. Such networks are a flexible framework for arbitrary function learning which have enjoyed a huge resurgence of interest in recent years in the fields of artificial intelligence, neuroscience, and cognitive science \citep[e.g.,][]{lecun2015,saxe2019}.

In an influential rebuttal of the use of neural network models for capturing relational reasoning, \citet{marcus:1999} argued that a broad class of recurrent neural networks were unable to learn a general solution to sequential equality problems and \citet{marcus:2001} argued that feed-forward neural networks are even unable to learn a general solution \blue{even to mathematical identity, which is arguably the simplest version of \emph{same}/\emph{different} reasoning conceptually}. These claims were subsequently challenged by the presentation of evidence that some forms of neural networks are able to learn (at least aspects of) \citeauthor{marcus:1999}'s equality tasks  \citep{dienes:1999,seidenberg:1999a,seidenberg:1999b,elman:1999,negishi:1999}, yet these examples were controversial. The resulting debate \citep[reviewed in][]{alhama:2019} revealed a striking lack of consensus on some of the ground rules regarding what sort of generalization would be required to show that the learned function was suitably abstract.

In the time since these debates, successful neural network models have been developed for tasks such as natural language inference \citep{Bowman:2015, Williams:2018}, question answering \citep{Rajpurkar:2016, Rajpurkar:2018}, and visual reasoning \citep{Johnson:2017}. In many respects, all of these tasks are far more complex than equality-based tasks. In light of these findings, it may be surprising that the debate over equality-based reasoning is unresolved \citep{alhama:2019}. Yet even recent work on equality-based reasoning tasks takes as its starting point the conclusion that neural networks are unable to succeed using standard architectures and general purpose learning algorithms \citep{alhama2018,weyde2019,weyde2018,kopparti2020}. Further, though tasks and contexts vary, work in both computer vision \citep{Kim:2018,Fleuret:2011,Bengio:2016} and machine reasoning \citep{raposo2017,santoro2017,santoro2018,palm2018} has presupposed that relational reasoning generally -- and sometimes equality-based reasoning specifically -- is difficult or impossible in standard network architectures.

\begin{figure}[tp]
  \centering
  \includegraphics[scale=0.30]{modelfigv1.pdf}
  \caption{Relational reasoning tasks. Green and red mark positive and negative training examples, respectively. The sequential task (Model~2) uses only positive instances, and a model succeeds if, prompted with $\alpha$, it produces a sequence $\beta \ \alpha$ where $\beta \neq \alpha$. For the hierarchical task (Model~3), we show that a model trained on the basic task (Model~1) is effective with no additional training.}
  \label{fig:tasks}
\end{figure}

Modern deep learning models have been so successful that it seems odd that they would be completely unable to learn equality-based reasoning tasks. We suspect these claims remain in the literature in part because only a narrow range of network architectures and representations were explored in the earlier debate, and in part because the debate predated many important innovations in neural network design. Thus we revisit the debate here, using a broader range of architectures and representations and adopting stringent criteria for generalization. In particular we explore random and pretrained representations, which have facilitated many of the successes of modern artificial intelligence \citep{CollobertWeston:2011,Mikolov-etal:2013,pennington-socher-manning:2014:EMNLP2014,Peters-etal:2018,Devlin-etal:2019}. The use of pretrained representations to solve downstream tasks in particular is argued to be a hallmark of natural learning systems \citep{zador2019}, has been an important feature of historical models from cognitive science \citep[e.g.,][]{landauer1997,mcrae1993}, and is essential in the latest wave of state-of-the-art natural language processing models \citep{Devlin-etal:2019,Liu:2019,Radford:2019,Brown:2020}.

In our current work, we model three cases of equality-based reasoning that have featured prominently in discussions of the role of symbols in relational reasoning (\figref{fig:tasks}): (1) learning to discriminate pairs of objects that exemplify the relation \emph{same} or \emph{different}, (2) learning sequences with repeated \emph{same} elements \citep{marcus:1999}, and (3) learning to distinguish hierarchical \emph{same} and \emph{different} relations in a context with pairs of pairs exemplifying these relations \citep{Premack:1983}. Across these three models, we find strong support for their ability to learn equality relations. These results should serve to revise the conclusions of the earlier debate.

\citet{marcus:1999} and \citet{marcus:2001} showed experimentally that certain neural networks could not generalize the equality relation to stimuli unseen in training. We agree with this claim (and support it with a direct mathematical argument). But we show that the claim is specific to networks that use particular kinds of representations, rather than neural networks in general. The representations that are problematic for this task are \tech{featural} representations (a term that we define in more detail below): representations where either specific properties (e.g., shape, color) or entire items are represented as discrete dimensions in the network's inputs.

Marcus and colleagues concluded from their results that neural networks need to have primitive symbolic operators to solve equality-based relational reasoning tasks, which is a solution that has been pursued in recent machine learning research \citep{weyde2019,weyde2018, kopparti2020}. On this point, we disagree. Our experiments show that networks without such primitives can solve a range of these tasks using the sort of random or pretrained representations that are now the norm throughout artificial intelligence research. Overall, these findings suggest that some essential aspects of symbolic reasoning can emerge from entirely data-driven, non-symbolic learning processes.

Our work here makes three contributions. First, we resolve this longstanding debate by demonstrating neural networks are able to learn equality relations when provided with pretrained or random representations. Second, we modify the standard architecture of a recurrent neural network to allow it to learn the sequential equality task with no negative feedback. Negative evidence was dismissed as an unreasonably strong learning regime in the original debate over these issues \citep[e.g.,][]{marcus:1999a}, and we show that this learning regime is not necessary. Third, we show that a model pretrained on the simple equality task can achieve zero-shot generalization (generalization with no new training instances) to the hierarchical equality task, suggesting that pretraining might provide an account of how some organisms succeed on hard relational learning tasks. We believe these three contributions represent significant progress in our understanding of neural networks' ability to perform equality-based reasoning.  Taken together, these contributions lay the groundwork for further non-symbolic neural network models of relational reasoning and abstract thought more broadly.

\blue{In all our experiments, we define \emph{same} and \emph{different} in terms of mathematical identity. These are the terms of the original debate, and learning these unambiguous relations is likely a prerequisite for learning real-world equality tasks grounded in some perceptual domain, such as a vision network trained for facial recognition \citep{Deepface:2021}. Thus, following the protocols of \citet{marcus:1999} and \citet{marcus:2001} as closely as possible, we assign every object a unique representation that is reliably retrieved by the model. We demonstrate that, starting from such pre-individuation, general solutions to equality relations can be learned if the right representations are used.}

\section{General methods: Designing theoretical models of equality learning}

We begin by discussing two critical design considerations for our models: (1) the standards for generalization by which models should be evaluated and (2) the type of representations they should use. To summarize this discussion: we select generalization tasks with fully disjoint training and test vocabularies to provide the most stringent test of generalization. Next, we show analytically that featural representations, which represent either object identities or object properties as discrete representational dimensions, limit successful out-of-sample generalization. Thus, we adopt randomly initialized representations or random representations that have been pretrained for our subsequent models. The studies reported in this paper were not preregistered. The datasets used in this paper are publicly available online.\footnote{All models, datasets, and code in this paper are available at \url{https://github.com/atticusg/NeuralEqualityExperiments} \citep{ourgit}.}

\subsection{Generalization}

The standard approach to training and evaluating neural networks is to choose a dataset, divide it randomly into training and test sets, train the system on the training set, and then use its performance on the test set as a proxy for its capacity to generalize to new data. There is a sizable literature focused on ensuring that models learn from the training set in ways that allow them to generalize; for a rich overview, see \citealt{Goodfellow-et-al-2016}, Part~II.

The standard approach is fine for many purposes, but it raises concerns in a context in which we are trying to determine whether a network has truly acquired a global solution to a target function. In particular, where there is any kind of overlap between the training and test vocabularies,
we can't rule out that the network might be primarily taking advantage of idiosyncrasies in the underlying dataset to ``cheat''. This cheating would happen because the network would simply memorize aspects of the training set and learn a local approximation of the target function that happens to provide traction during assessment. In recent years, these concerns have motivated two complementary innovations in model assessment within AI: \tech{systematic generalization tasks} and \tech{adversarial testing}.

In systematic generalization tasks, one centers the model evaluation around a specific phenonemon that is not represented directly in the test set but that is determined by the training set together with an assumption about how knowledge should generalize. For example, building on ideas from \citet{Lake2018}, \citet{wu2021} define test sets around specific adjective--noun modification structures $\mathit{A\, N}$, ensuring that the training set includes only examples involving $\mathit{A\, N'}$ and $\mathit{A'\, N}$ for $\mathit{A} \neq \mathit{A}'$ and $\mathit{N} \neq \mathit{N}'$. Given a general assumption of systematicity   \citep{fodor1988}, we expect this training set to support learning to make accurate predictions for $\mathit{A\, N}$, and the design of the train--test split gives us confidence that such predictions are not based on mere memorization of $\mathit{A\, N}$ itself. For other examples involving systematic generalization tests, see \citealt{geiger2020,goodwin-etal-2020-probing,Hupkes2020,yanaka-etal-2020-neural}.

In adversarial testing (sometimes called \tech{challenge testing}), one uses behavioral assessments to identify examples and phenomena that fool top-performing models but are natural for humans. This can follow a similar pattern to systematic generalization tasks, but here the models are generally ones that have been trained on large benchmark datasets intended to circumscribe a specific capability. The intent of the adversarial test is to show that models trained on these resources have persistent gaps and other weaknesses. The intuitive idea behind adversarial testing traces to \citet{Winograd:1972} (see also \citealt{Levesque:2013}), and it has been used effectively in a number of domains, including object recognition in digital images \citep{Goodfellow-etal:2015}, basic factual question answering \citep{D17-1215}, and natural language inference \citep{glockner-etal-2018-breaking,nie2019analyzing}. More recently, adversarial testing has been extended to include training on adversarial examples in order to develop more robust models \citep{nie-etal-2020-adversarial,bartolo-etal-2020-beat,potts-etal-2020-dynasent,kiela-etal-2021-dynabench}.

In our work, we adopt elements of both these modes for assessing generalization. Following \citet{marcus:1999}, we propose that networks must be evaluated on assessment sets that are completely disjoint in every respect from the training set, all the way down to the entities involved. For example, below, we train on pairs $(a, a)$ and $(a, b)$, where $a$ and $b$ are representations from a train vocabulary $V_{T}$. At test time, we create a new assessment vocabulary $V_{A}$, derive equality and inequality pairs $(\alpha, \alpha)$ and $(\alpha, \beta)$ from that vocabulary, and assess the trained network on these new examples. This is an adversarial setting in service of a specific, systematic learning target (equality). In adopting these methods, we get a clear picture of the system's capacity to generalize, and we can safely say that its performance during assessment is a window into whether a global solution to identity has been learned. This is a very challenging setting for any machine learning model. For the sequential same--different task, we will see that it even requires us to depart from the usual formulations for predictive language models, in that such models standardly cannot even be evaluated on examples that are completely out of vocabulary.

\subsection{Representations}\label{sec:representations}

\input{reps-diagram}

Essentially all modern machine learning models represent objects using vectors of real numbers. However, there are important differences in how these vectors are used to encode the properties of objects. The method of representation chosen for a particular model impacts both whether there is a natural notion of similarity between entities and whether the model can generalize to examples unseen in training. These two attributes are deeply related; if there is a natural notion of similarity between vector representations, then models can generalize to inputs with representations that are similar to those seen in training.

We characterize two broad approaches to such property encoding -- which we call \tech{featural representations} and \tech{non-featural representations} -- and argue that the differences between them have not been given sufficient attention in the debate about the ability of neural networks to perform relational reasoning. We acknowledge that a dimension of any vector representation is a ``feature'', but we adopt a usage that is common in cognitive science, namely, that a feature is an interpretable semantic primitive.\footnote{The term \tech{distributed representations} is used to refer jointly to what we call property representations, random representations, and pretrained representations. We opted not to use this term because it does not seperate property representations from random and pretrained representations, which is the relevant division here. Distributed representations are often contrasted in the neural network literature with \tech{local} or \tech{localist} representations; as discussed below, here we define these terms specifically to refer to representations whose features correspond to specific entities.}

We ground our discussion in a hypothetical universe of blocks which vary by shape and color. \Figref{fig:entities} is a partial view of them, and \figref{fig:reps:localist}--\figref{fig:reps:pretrained} present four different ways of encoding the properties of these objects in vectors.

\subsubsection{Featural representations}

The defining characteristic of \tech{featural} vector representations is that each dimension encodes the value of a single, semantically intepretable property. The properties can be binary, integer-valued, or real-valued.

We use the term \tech{localist} for the special case of featural representations in which only objects are represented and there is a feature corresponding to each object. In \figref{fig:reps:localist}, each column represents the property of being an object, and every object is represented as a vector that has a single unit with value 1 (which is why these representations are often called ``one-hot'' vectors). There is no shared structure across objects; all are equally (un)related to each other as far as the model is concerned.

We will refer to featural representations that are not localist as \tech{property representations}. Here, column dimensions encode specific, meaningful properties of objects. In our example, we can represent the properties of being red and being blue with two different binary features, and the property of having a certain number of sides as a single integer feature, as in \figref{fig:reps:symbolic}. Unlike with localist representations, objects in this space can have complex relationships to each other, as encoded in the shared structure given by the columns.

\subsubsection{Non-featural representations}\label{sec:nonfeatural}

A \tech{non-featural representation} is a vector that encodes property values implicitly across many dimensions. Perhaps the simplest non-featural representations are \tech{completely random} vectors, as in \figref{fig:reps:random}. Random representations can be seen as the non-featural counterpart to localist representations. In both of these representation schemes, all the objects are equally (un)related to each other, since column-wise patterns are unlikely in random representations and, to the extent that they are present, they exist completely by chance. However, in random representations, all the column dimensions can contribute meaningfully to identifying objects, whereas a localist representation has only one vector unit that determines the identity of any given object.

\subsubsection{Pretraining}\label{sec:pretraining}

\begin{figure}[tp]
  \centering
  \resizebox{325pt}{!}{%
    \begin{tikzpicture}[

      font=\sf \large,
      >=LaTeX,

      rep/.style=
        rectangle,
        rounded corners=3mm,
        draw,
        very thick,
        minimum height =1cm,
        minimum width=1.61cm
      },
      function/.style=
        ellipse,
        draw,
        inner sep=1pt
      },
      gt/.style=
        rectangle,
        draw,
        minimum width=5mm,
        minimum height=4mm,
        inner sep=1pt
      },
      function/.style={
        rectangle,
        draw,
        minimum width=5mm,
        minimum height=4mm,
        inner sep=1pt
      },
      arrowconcat/.style=
        rounded corners=.25cm,
        dashed,
        thick,
        ->,
      },
      arrowfunction/.style=
        rounded corners=.25cm,
        thick,
        ->,
      }
      ]

      \node [rep, fill=black!20] (input) at (6,1){$E[i]$} ;

      \node [rep, fill=blue!40] (hidden) at (6,5){$h_{i}$} ;
      \node [gt, minimum width=1cm] (relu) at (6, 3-0.1) {$\ReLU( E[i]W_{xh} + b_{h})$};
      \draw [arrowfunction] (input) -- (relu) -- (hidden);

      \node [gt, minimum width=1cm] (softmax1) at (0,7-0.1) {$\mathbf{softmax}(h_{i}W_{hy}^{1} + b_{y}^{1})$};
      \node [gt, minimum width=1cm] (softmax2) at (6,7-0.1) {$\mathbf{softmax}(h_{i}W_{hy}^{2} + b_{y}^{2})$};
      \node [gt, minimum width=1cm] (softmax3) at (12,7-0.1) {$\mathbf{softmax}(h_{i}W_{hy}^{3} + b_{y}^{3})$};

      \node [rep, fill=red!40] (output1) at (0,9){$y_{i,1}$} ;
      \node [rep, fill=red!40] (output2) at (6,9){$y_{i,2}$} ;
      \node [rep, fill=red!40] (output3) at (12,9){$y_{i,3}$} ;

      \draw [arrowfunction] (hidden) -- (softmax1) -- (output1);
      \draw [arrowfunction] (hidden) -- (softmax2) -- (output2);
      \draw [arrowfunction] (hidden) -- (softmax3) -- (output3);

    \end{tikzpicture}
  }
  \caption{Pretraining architecture shown for three pretraining tasks. The network is trained as a classifier, but the target of learning is the matrix of input representations $E[i]$, which are imbued with structure from the tasks via backpropagation.}
  \label{fig:models:pretraining}
\end{figure}

Random representations are a starting point that encodes object identity, but we can \tech{pretrain} these representations via a learning process, imbuing them with rich structure that implicitly encodes property values across many dimensions. \Figref{fig:reps:pretrained} provides a simple example. This matrix is the results of pretraining the representations in \figref{fig:reps:random} on three tasks: whether the object is blue, whether the object is red, and the number of sides the object has. Superficially, the two matrices look equally random, but the random representations in \figref{fig:tsne-random} have no such structure, while the pretrained representations in \figref{fig:tsne-pretrained} do. For example, there is a line that separates blue and red objects.

In our main experiments, we explore pretraining as a path to more efficient learning. There are many potential approaches to pretraining that could be effective in this context. We adopt a simple one based in a multi-task classifier. Intuitively, this works as follows: random representations (vectors) are paired with  labels corresponding to properties like those in our illustration: whether the object is blue, whether the object is red, and so forth. The multi-task classifier is trained as usual to predict these labels. However, rather than using the trained classifier to predict such labels, we focus instead on the way the input random representations are affected (pretrained) by this learning process. Once the process is complete, the richly structured inputs that result are then used in other tasks.

In detail, our pretraining model is a feed-forward network with a multi-task objective. For an example $i$ and task $j$, the model is defined as follows:
\begin{align}
  h_{i} &= \ReLU( E[i]W_{xh} + b_{h}) \\
  y_{i,j} &= \mathbf{softmax}(h_{i}W_{hy}^{j} + b_{y}^{j})
\end{align}
Here, $E[i]$ is the vector representation for example $i$ in an embedding matrix $E$ of dimension $|V| \times m$, where $V$ is the ``vocabulary'' of vectors to be pretrained. These representations are multiplied by a vector of weights $W_{xh}$ of dimension $m \times n$ and a bias vector $b_{h}$ of dimensions $n$ is added to the result. These two steps create a linear projection of the input representation, and the bias term is the value of this linear projection when the input representation is the zero vector. Then, the non-linear activation function $\ReLU(x) = \max(0, x)$ is applied element-wise to this linear projection. This non-linearity is what gives the neural model more expressive power than a logistic regression \citep{Cybenko:1989,Hornik:Stinchcombe:White:1989}. The result is the hidden representation $h_{i}$.

The hidden representation is the input to a separate classification layer for each class $j$. Each of these classification layers is defined by weights $W_{hy}^{j}$ and bias $b_{y}^{j}$. Each of these again defines a linear projection, now of $h_{i}$. The result is fed through the softmax activation function: $\mathbf{softmax}(x)_{i} = \frac{\exp{x_{i}}}{\sum_{j} \exp{x_{j}}}$. This creates a probability distribution over the classes (in our tasks, `positive' and `negative'). For a given input and task $j$, the model computes this probability distribution and the input is categorized as the class for $j$ with the higher probability.

\Figref{fig:models:pretraining} depicts this model in detail for 3 tasks ($J = 3$). The diagram helps reveal that the embedding $E$ and the parameters $W_{xh}$ and $b_{h}$ are jointly trained against all the tasks, whereas the parameters $h_{i}W_{hy}^{j}$ and $b_{y}^{j}$ are specific to each task $j$.

The overall objective of the model is to maximize the sum of the task objective functions. For $|V|$ examples, $J$ tasks, and $K_{j}$ the number of classes for task $j$:
\begin{equation}
  \max(\theta)
  \quad
  \frac{1}{|V|}
  \sum_{i=1}^{|V|}
  \sum_{j=1}^{J}
  \sum_{k=1}^{K_{j}}
  y^{i,j,k} \log \left( h_{\theta}(i)^{j,k} \right)
\end{equation}
where $y^{i,j,k}$ is the correct label for example $i$ in task $j$ and $h_{\theta}(i)^{j,k}$ is the predicted value for example $i$ in task $j$. We use $\theta$ to abbreviate all the model parameters: $E$, $W_{xh}$, $b_{h}$, and $W_{hy}^{j}$ and $b_{y}^{j}$ for each task $j$.

Our motivation for pretraining is to update the embedding $E$ so that its representations encode properties that can be used by subsequent models. To achieve this, we backpropagate errors through the network and into $E$. This backpropagation is the step that pretrains $E$ itself.

For the experiments reported below, we initialize $E$ randomly and then, for pretraining on $J$ tasks, we create a random binary vector of length $J$ for each row in $E$. Each dimension (task) in $J$ is independent of the others. We always pretrain for 10 epochs, where each epoch consists of an example for each item in the vocabulary. This choice is motivated primarily by computational costs; additional pretraining epochs greatly increase experiment run-times, though they do have the potential to imbue the representations with even more useful structure. Pretraining with the optimal hyperparameter settings always led to perfect accuracy on the pretraining tasks.

Pretraining need not be restricted to input representations; all the parameters of a model can be pretrained, offering the possibility that networks might be used as modular components to solve more complex tasks. We realize this possibility with our Experiment~4, where a model pretrained on a simple equality is used as a modular component to compute hierarchical equality.

\subsubsection{Localist and binary property representations prevent generalization}

Featural representations -- both localist and property -- have the appealing property that they are easy for researchers to interpret because of the tight correspondence between column dimensions and properties. However, this transparency actually inhibits neural networks from discovering general solutions. The core insight is that networks cannot learn anything about column dimensions that are not represented in their training data; whatever weights are associated with those dimensions are unchanged by the learning process, so predictions about those dimensions remain random at test time.

In order to see this, we need attend to the details of how neural models are trained. All the neural models in this paper are trained using the back-propagation learning algorithm. An easily observed fact about this algorithm is that, if a unit of the input vector is always zero during training, then any weights connected to that unit and only that unit will not change from their initialized values during training. This means that, when a standard neural model is evaluated on an input vector that has a non-zero value for a unit that was zero throughout training, untrained weights are used to make predictions, and so the network's behavior is unpredictable.

Of all the representation schemes we consider, localist representations are the one that most severely limit generalization. No two representations share a non-zero unit, and so when models are presented with inputs unseen in training, untrained weights are used and the resulting behavior is unpredictable. In addition, all such representations are orthogonal and equidistant from one another, so there is no notion of similarity, and consequently there is no usable transfer of information from training to assessment.

Property representations with binary features also limit generalization, though less severely than localist representations. Localist representations prevent generalization to \emph{entities} unseen during training, while binary feature representations prevent generalization to \emph{properties} unseen during training. For example, if color and shape are represented as binary features, and a red square and blue circle are seen in training, then a model could generalize to the unseen entities of a blue circle or a red square. However, if no entity that is a circle is seen during training, then the binary feature representing the property of being a circle is zero throughout training and untrained weights are used when the model is presented with a entity that is a circle during testing, which once again results in unpredictable behavior.

Property representations with analog features do not inhibit generalization in the same way. If height is represented as an analog feature, then a single unit represents all height values and is always non-zero. Of course, if the height feature is held out entirely during training (i.e., seen only at test time), then generalization will be limited just as it is for binary property representations.

Importantly, non-featural representations do not inhibit generalization in these ways, because all units for all representations are non-zero and the network can learn parameters that create complex associations between these entities and its task labels. These representations then can be generalized to new entities, even those unseen during training. \blue{In machine learning, learned non-featural representations are now the norm, not only because they address this limitation but also because they have proven superior even in settings where all column dimensions are well represented in the training data.}

Recent work in machine learning \citep{weyde2019,weyde2018,kopparti2020} attempts to overcome the analytic limitations of binary featural representations by modifying standard neural architectures to have symbolic primitives or changing network weight priors. In our work, we instead opt for non-featural representations, which do not have this analytic limitation and are the norm in state-of-the-art artificial intelligence models. There is no need to introduce symbolic primitives or modify network weight priors when non-featural representations are used.

\input{fourmodels}

\section{Experiment 1: A feed-forward neural model of same--different relations}\label{sec:equality}

We first investigate whether a basic supervised feed-forward neural network can learn the equality relation in the strict setting we describe above, where the training and test vocabularies are disjoint.

\subsection{Methods}

Our basic model for equality is a feed-forward neural network with a single hidden representation layer. The model is depicted graphically in \Figref{fig:models:equality} and defined as follows:
\begin{align}
h &= \ReLU([a;b]W_{xh} + b_{h}) \label{eq:x2h}\\
y &= \mathbf{softmax}(hW_{hy} + b_{y}) \label{eq:h2y}
\end{align}
The input is a pair of vectors $(a, b)$, which correspond to the two stimulus objects. These vectors are non-featural representations that do not have features encoding properties of the objects or their identity (though they may be pretrained). These are concatenated to form a single vector $[a;b]$ of dimension $2m$, which is the simplest way of merging the two representations to form a single input.

This representation is multiplied by a matrix of weights $W_{xh}$ of dimension $2m \times n$ and a bias vector $b_{h}$ of dimension $n$ is added to this result, where $n$ is the hidden layer dimensionality, with the $\ReLU$ activation applied element-wise to the result. This yields the hidden representation $h$, which is multiplied by a second matrix of weights $W_{hy}$, dimension $n \times 2$, and a bias term $b_{y}$ (dimension $2$) is added to this. A final softmax activation function creates a probability distribution over the classes. For a given input, the model computes this probability distribution and the input is categorized as the class with the higher probability.

During training, this model is presented with positive and negative labeled examples and the parameters $W_{xh}$, $W_{hy}$, $b_{y}$, and $b_{h}$ are learned using backpropagation with a cross entropy loss function. This function is defined as follows, for a corpus of $N$ examples and $K$ classes:
\begin{equation}
\max(\theta)
\quad
\frac{1}{N}
\sum_{i=1}^{N}
\sum_{k=1}^{K}
y^{i,k} \log(h_{\theta}(i)^{k})
\end{equation}
where $\theta$ abbreviates the model parameters ($W_{xh}$, $W_{hy}$, $b_{y}$, $b_{h}$), $y^{i,k}$ is the actual label for example $i$ and class $k$, and $h_{\theta}(i)^{k}$ is the corresponding prediction.

During testing, this model is tasked with categorizing inputs unseen during training. It is straightforward to show that a network like this is capable of learning equality as we have defined it. Indeed, in our Appendix, we provide one possible analytic solution to the equality relation using this neural model. Here we illustrate with a small example network that maps all identity pairs to $[0.5, 0.5]$ and all non-identity pairs to $[y, 1-y]$ where $y > 0.5$, which supports a trivial classification rule:
\setlength{\arraycolsep}{4pt}
\begin{equation}
\mathbf{softmax}\left(
  \ReLU\left(
    [a;b]
    \left(
      \begin{array}[c]{@{} *{4}{r} @{}}
        1 & 0 & -1 & 0 \\
        0 & 1 & 0 & -1 \\
        -1 & 0 & 1 & 0 \\
        0 & -1 & 0 & 1
      \end{array}
    \right)
    +
    \mathbf{0}
  \right)
  \left(
    \begin{array}[c]{@{} r r @{}}
      1 & 0 \\
      1 & 0\\
      1 & 0\\
      1 & 0\\
    \end{array}
  \right)
  +
  \mathbf{0}
\right)
\end{equation}

This result shows that equality in our sense is learnable in principle, but it doesn't resolve the question of whether networks can find this kind of solution given finite training data. To address this issue, we train networks on a stream of pairs of random vectors. Half of these are identity pairs $(a, a)$, labeled with `positive', and half are non-identity pairs $(a, b)$, labeled with `negative'. Trained networks are assessed on the same kind of balanced dataset, with vectors that were never seen in training so that, as discussed earlier, we get a clear picture of whether they have found a generalizable solution.

We implemented this network using the multi-layer perceptron from scikit-learn \citep{scikit-learn}, and we conducted a wide hyperpameter search. See our Appendix\ for a full specification of our experimental protocol. In the main text, we graph results for the single best hyperparameter setting, reflecting our goal of assessing the possibility of high performance in this task from a network of this type. All the models are trained on balanced datasets, and they never see the same input more than once. The test set is a fixed set of 500 vectors, disjoint from the training sets and also balanced across the two classes.

\subsection{Results}

\begin{figure}
 \centering
 \includegraphics[width=0.6\linewidth]{fig/equality-pretrain-compare-train_size-pretrained-embed_dim=None.pdf}
 \caption{Experiment 1 results: feed-forward neural networks with one hidden layer trained on our simple equality task (10-dimensional inputs, 100-dimensional hidden layers). The `no pretraining' model is provided random representations and the `$k$-task pretraining' models are provided random representations that are grounded in $k$ binary property domains.}
 \label{fig:basic-equality-pretrain}
\end{figure}

\Figref{fig:basic-equality-pretrain} shows our results, for a model with an embedding dimension of 10 and a hidden-layer dimension of 100. (In the Appendix, \Figref{fig:model1} provides results for other network dimensionalities, and \figref{fig:train-results:e1} provides comparable results for evaluations on the training set.) The representations used in these experiments are random representations that were pretrained using a linear classifier for 0, 3, 5, or 10 different independent binary feature discrimination tasks (with 0 corresponding to purely random representations). For example, following \figref{fig:reps}, a three-task model might be trained to encode binary properties that we might gloss as `being blue', `having four sides', and `being red'. For all representations, this neural model reached above-chance performance almost immediately, but required upwards of 1,000 examples to achieve near perfect accuracy.   Interestingly, we observed a clear speed-up with pretraining, with more pretraining tasks resulting in the largest gains. It seems that, by grounding our representations in ``property domains'' (as represented by the different task dimensions), we imbue them with implicit structure that makes learning easier.

\subsection{Discussion}

Our assessment pairs have nothing in common with the training pairs except insofar as both involve vectors of real numbers of the same dimensionality. During training, the network is told (via labels) which pairs are equality pairs and which are not, but the pairs themselves contain no information about equality per se. It thus seems fair to us to say that these networks have learned equality -- or at least how to simulate that relation with near perfect accuracy. Further, the use of representations that are structured by pretraining results in faster learning.

\section{Experiment 2: A recurrent neural model of  sequential same--different}\label{sec:lms}

Our first model is simple and successfully learns equality. However, this model is supervised with both positive and negative evidence. In the initial debate around these issues, supervision with negative evidence was dismissed as an unreasonably strong learning regime \citep[e.g.,][]{marcus:1999a}. While this argument likely holds true for language learning \citep[in which supervision is generally agreed not to be binary or direct;][]{brown:1970,chouinard2003}, it is not necessarily true for learning more generally. Nevertheless, learning of sequential rules without negative feedback is possible for infants \citep{marcus:1999,rabagliati:2019}. In experiments of this type, infants are presented with a set of positive examples of the form ABA. Then their responses are measured for examples using entirely new stimuli that either conform to the ABA regularity or not. Our next model explores whether neural networks can learn this sequential equality task in the same challenging regime with no negative supervision.

\subsection{Methods}

To explore learning with only positive instances, we use a neural LSTM language model, a recurrent network with the ability to selectively forget and remember information \citep{hochreiter:1997}. Language models are sequential: at each timestep, they predict an output given their predictions about the preceding timesteps. As typically formulated, the prediction function is just a classifier: at each timestep, it predicts a probability distribution over the entire vocabulary of options, and the item with the highest probability is chosen as a symbolic output. This output becomes the input at the next timestep, and the process continues.

As we noted above, this standard formulation will not work in situations in which we want to make predictions about test items with an entirely disjoint vocabulary from the training sample. The classifier function will get no feedback about these out-of-vocabulary items during training, and so it will never predict them during testing.

To address this issue, we reformulate the prediction function. Our proposal is to have the model predict output vector representations -- instead of discrete vocabulary items -- at each timestep. During training, the model seeks to minimize the distance between these output predictions and the representations of the actual output entities. During assessment, we take the prediction to be the item in the entire vocabulary (training and assessment) whose representation is closest to the predicted vector (in terms of Euclidean distance). This fuzzy approach to prediction creates enough space for the model to predict sequences from an entirely new vocabulary.

The specific model we use for this is as follows:
\begin{align}
h_{t} &= \textbf{LSTM}(x_{t}, h_{t-1}) \label{eq:lstm-recur}\\
y_{t} &= h_{t}W + b\label{eq:lstm-predict}
\end{align}
This holds for $t > 0$, and we set $h_{0} = \mathbf{0}$. $\textbf{LSTM}$ is a long short-term memory cell \citep{hochreiter:1997}. We visualize this model in \figref{fig:reps:sequence}.

The input is a sequence of vectors $x_1, x_2, x_3, \dots$, each of dimension $m$, which correspond to a sequence of stimulus objects. These vectors are, again, non-featural representations that do not have features encoding properties of the objects or their identity, though they may be pretrained to encode such properties more abstractly.

At each timestep $t$, the input vector $x_t$ is fed into the $\textbf{LSTM}$ cell along with the previous hidden representation $h_{t-1}$. The defining feature of an $\textbf{LSTM}$ is the ability to decide whether to store information from the current input, $x_t$, and whether to remember or forget the information from the previous timestep $h_{t-t}$. The output of the $\textbf{LSTM}$ cell is the hidden representation for the current time step $h_t$. The dimension of the hidden representations is $n$. The hidden representation is multiplied by a matrix $W$ with dimensionality $n \times m$ to produce $y_t$. This result, $y_t$, is a linear projection of the hidden representation into the input vector space, which is necessary because $y_t$ is a prediction of what the next input, $x_{t+1}$, will be.

The objective function is as follows:
\begin{equation}
\max(\theta)
\quad
-\frac{1}{N}
\sum_{i=1}^{N}
\sum_{t=1}^{T_{i}}
\left\| h_{\theta}\left(x^{i, 0:{t-1}}\right) - x^{i,t} \right\|^{2}
\end{equation}
for $N$ examples. Here, $T_{i}$ is the length of example $i$. As before, $\theta$ abbreviates the parameters of the model as specified in \dasheg{eq:lstm-recur}{eq:lstm-predict}. We use $h_{\theta}(x^{i, 0:{t-1}})$ for the vector predicted by the model for example~$i$ at timestep~$t$, which is compared to the actual vector at timestep $t$ via squared Euclidean distance (i.e., the mean squared error).

We implemented this recurrent LSTM network for the sequential ABA task using PyTorch \citep{pytorch}. As in our previous experiment, we conducted a wide hyperparameter search (see our Appendix\ for details). In the main text, we graph results for the single best hyperparameter setting. We trained and tested on vocabularies of size 20, which are reconstructed between each run.

Our Appendix\
provide an analytic solution to the ABA task using this model. To see how well the model performs in practice, we trained networks on sequences \texttt{<s> a b a </s>}, where $\texttt{b} \neq \texttt{a}$. We show the network every such sequence during training, from an underlying vocabulary of 20 items (creating a total of 380 examples). To assess how well the model learns this pattern, we seed it with \texttt{<s> x} where \texttt{x} is an item from a disjoint vocabulary from that seen in training, and we say that a prediction is accurate if the model continues with \texttt{y x </s>}, where \texttt{y} is any character (from the training or assessment vocabulary) except \texttt{x}. In our experiments, we use a test vocabulary of 26 items, which creates 52 distinct \texttt{y x </s>} continuations and hence 52 distinct test examples.

\subsection{Results}

\begin{figure}
 \centering
 \includegraphics[width=0.6\linewidth]{fig/fuzzy-lm-pretrain-compare-train_size-pretrained-embed_dim=None.pdf}
 \caption{Experiment 2 results: LSTM recurrent neural networks trained on our sequential equality task (2-dimensional inputs, 100-dimensional hidden layers). The `no pretraining' model is provided random representations and the `$k$-task pretraining' models are provided random representations that are grounded in $k$ binary property domains via pretraining. All the training examples are presented at once over multiple epochs.}
 \label{fig:fuzzy-lm-pretrain-results}
\end{figure}

\Figref{fig:fuzzy-lm-pretrain-results} shows our results, for networks with 2-dimensional embeddings and 100-dimensional hidden representations. (\Figref{fig:model2} provides results for a wide range of network dimensionalities.) Unlike for the previous equality experiment, we found that we had to allow the model to experience multiple epochs of training on the same set in order to succeed, and tens of thousands of training examples were necessary. We considered a range of representations (as in Experiment~1), and the model was again successful with all representations. However, unlike in Experiment~1, we do not find evidence in favor of pretraining for this task.

\Figref{fig:train-results:e2} provides training-set results that are comparable to those in \figref{fig:fuzzy-lm-pretrain-results}. These models very quickly learn to perform with near perfect accuracy on the training set, creating a large gap between training-set performance and test-set performance. This contrasts with our other models, for which the differences between these two modes of evaluation are small. This difference likely traces to the nature of language modeling tasks (compared with classifiers) as well as our decision to allow the model to experience multiple epochs of the same training data.

\subsection{Discussion}

These sequential models are given no negative examples and they must predict into a totally new vocabulary. Despite these challenges, they succeed at learning the underlying patterns in our data. On the other hand, the learning process is slow and data-intensive. We hypothesized that grounding representations in property domains via pretraining might lead to noticeable speed-ups, as it did in for our simple same-different task (Experiment~1), but we did not see this effect in practice. We speculate that there may be model variants that reduce these demands, given that learning is in principle possible in this architecture, but we leave them to future work.

\section{Experiment 3: A feed-forward neural model of hierarchical same--different relations}\label{sec:premack}

Given the strong results found for simple equality relations, we can ask whether more challenging equality problems are also learnable in our setting. The hierarchical equality task used by \citet{Premack:1983} is an interesting test case: given a pair of pairs $((a,b), (c,d))$, the label is `positive' if $(a = b)$ and $(c = d)$ or $(a \neq b)$ and $(c \neq d)$. The mixed cases (i.e., $(a = b)$ and $(c \neq d)$; $(a \neq b)$ and $(c = d)$) are labeled `negative'.

\citeauthor{Premack:1983} suggested that the ability exemplified by this task -- reasoning about hierarchical \emph{same} and \emph{different} relations -- could represent a form of symbolic abstraction uniquely enabled by language. Given the non-symbolic nature of our models, our simulations provide a test of this hypothesis, though we should look critically at their ability to find good solutions with reasonable amounts of training data.

\subsection{Methods}

We can approach this task using the same model and methods as we used for equality, with the relatively minor change of providing the network four vector representations instead of two. We found that feed-forward neural networks with only one hidden layer required nearly 100,000 training examples to solve this task (see \figref{fig:model1:premack}).  We hypothesized that a single hidden layer network might be suboptimal here. This task is intuitively hierarchical: if one works out the equality labels for each of the two pairs, then the further classification decision can be done entirely on that basis. Our current neural network might be too shallow to find this kind of decomposition. To address this issue, we use a feed forward network with two hidden layers. We visualize this model in \Figref{fig:models:premack-deep} and we define
\begin{align}
h_{1} &= \ReLU([a;b;c;d]W_{xh} + b_{h_{1}}) \label{eq:x2h1}\\
h_{2} &= \ReLU(h_{1}W_{hh} + b_{h_{2}}) \label{eq:x2h2}\\
y &= \mathbf{softmax}(h_{2}W_{hy} + b_{y}) \label{eq:h2y2}
\end{align}

We implemented this network using PyTorch and conducted a wide hyperparameter seach (see our Appendix\ for details). In the main text, we graph results for the single best hyperparameter setting. The training and testing protocol is the same as in Experiment~1, and we further ensure that the train and test sets are balanced across the four distinct input types for the hierarchical task (same/same, different/different, same/different, and different/same).

\subsection{Results}

\Figref{fig:premack-h2-pretrain} shows our results for networks with 10-dimensional embeddings and 100-dimensional hidden layers. (\Figref{fig:model3a} shows results for other network dimensionalities.) We again considered a range of representations, and again the network succeeded across this range, with pretraining increasing performance dramatically. The network required more than 20,000 training instances to reach top performance, and upwards of 10,000 examples with pretrained representations.

\subsection{Discussion}

Our model with two hidden layers requires vastly more data than human participants get in similar experiments. For example, sequential rule learning experiments typically involve short exposures in the range of dozens to hundreds of examples \citep[e.g.,][]{marcus:1999,endress2005}. Thus, it is worth asking whether there are other solutions that would be more data efficient and more in line with human capabilities. We next seek to further capitalize on the hierarchical nature of this task by defining a modular pretraining regime in which previously learned capabilities are recruited for new tasks.

\section{Experiment 4: A tree-structured model of hierarchical same--different relations pretrained on simple equality}\label{sec:modular}

Our successful results training neural networks on simple equality suggested another strategy for solving the hierarchical equality task. Rather than requiring our networks to find solutions from scratch, we pretrained them on basic equality tasks and then used those parameters as a starting point for learning hierarchical equality. This set of simulations was conceptually similar to our previous experiments with pretrained input representations, but now we pretrained an entire subpart of the model, rather than just input representations. This approach parallels the experimental paradigm used by \citet{thompson:1997}, in which chimpanzees that received pretraining on a basic equality (\emph{same}/\emph{different} judgment) task -- but not naive champanzees -- succeed in a hierarchical equality task.

\begin{figure*}
  \centering
  \begin{subfigure}[t]{0.48\linewidth}
    \centering
    \includegraphics[width=1\linewidth]{fig/flatpremack-h2-pretrain-compare-train_size-pretrained-embed_dim=None.pdf}
    \caption{Experiment 3 results: feed-forward neural networks with two hidden layers trained on our hierarchical equality task (10-dimensional inputs; 100-dimensional hidden layers).}
    \label{fig:premack-h2-pretrain}
  \end{subfigure}
  \hfill
  \begin{subfigure}[t]{0.48\textwidth}
    \centering
    \includegraphics[width=1\linewidth]{fig/input-as-output-pretrain-compare-train_size-pretrained-embed_dim=None.pdf}
    \caption{Experiment 4 results: simple equality networks (with 25-dimensional inputs and, in turn, 50-dimensional hidden representations) applied to the hierarchical equality task as pretrained components. Even with no additional training instances for this task (``zero shot''), all models achieve greater than chance accuracy, and even modest amounts of additional training on the task lead to excellent performance. Additionally pretraining the input representations leads to modest improvements.}
    \label{fig:premack-pretraining-results}
  \end{subfigure}
  \caption{Results for (a) hierarchical sequential equality task without pretraining on simple equality and (b) with pretraining on simple equality. The `no pretraining' models are provided random representations and the `$k$-task pretraining' models are provided random representations that are grounded in $k$ binary property domains via pretraining learning tasks. The Experiment~3 model requires vastly more task-specific training data than the Experiment~4 model to achieve good results, which helps to show the value of modular reuse of pretrained components.}
\end{figure*}

\subsection{Methods}

The hierarchical equality task requires computing the equality relation three times: compute whether the first two inputs are equal, compute whether the second two inputs are equal, then compute whether the truth-valued outputs of these first two computations are equal. We propose to use the same network pretrained on basic equality to perform all three equality computations. The model is depicted in \figref{fig:models:premack} and defined as follows:
\begin{align}
h_1 &= \ReLU([a;b]W_{xh} + b_{h}) \label{eq:e4:1}\\
h_2 &= \ReLU([c;d]W_{xh} + b_{h})\\
h_3 &= \ReLU([h_1;h_2]W_{xh} + b_{h}) \\
y &= \mathbf{softmax}(h_3W_{hy} + b_{y}) \label{eq:e4:y}
\end{align}
Here, $W_{xh}$, $W_{hy}$, $b_h$, and $b_y$ are the parameters from the model in equations \dasheg{eq:x2h}{eq:h2y} already trained on basic equality. Crucially, the same parameters, $W_{xh}$ and $b_h$, are used three times: twice to compute representations encoding whether a pair of input entities are equal ($h_1$, $h_2$), and once to compute a representation ($h_{3}$) encoding whether the truth values encoded by $h_1$ and $h_2$ are equal. This final representation is then used to compute a probability distribution over two classes, and the class with the higher probability is predicted by the model.\footnote{\blue{A clear limitation of this approach is that it presupposes the hierarchical nature of the task rather than learning it from the data. Recent developments with modular networks and routing networks might open up a path to removing this limitation \citep{Andreas-etal:2016,chang2018automatically,Cases-etal:2019,Kirsch-etal:2018}. We briefly return to this point in our `General discussion' below.}}

We implemented this network using PyTorch using the same protocols as in Experiments 1--3 (see our Appendix\ for details). In the main text, we graph results for the single best hyperparameter setting. The training and testing protocol matches the one used in Experiments~3.

\subsection{Results}

\Figref{fig:premack-pretraining-results} shows our results for networks with 25-dimensional inputs, which sets the dimensionality of the hidden representations to 50. (See \Figref{fig:model3a} for results for other network dimensionalities.) All the models have above chance performance after being trained only on the simple equality task -- that is, they achieve zero-shot generalization to the hierarchical task and within two thousand examples, the models achieve near perfect accuracy. Additionally pretraining the input representations leads to modest but consistent gains in terms of learning speed. (In \figref{fig:train-results:e4}, we provide comparable training set assessments; in that context, pretraining has the opposite effect, slightly slowing down learning.)

\subsection{Discussion}

It is remarkable that a model trained only on equality between entities is able to get traction on a problem that requires determining whether equality holds between the truth values encoded in two learned representations. What is more, even small amounts of additional training data lead to excellent performance on the task. This shows the value of pretraining regimes involving entire networks, and it begins to show how trained networks can serve as modular components that are useful for solving more complex tasks.

Intuitively, this problem presents four different input class-types: the two `positive' classes (same/same and different/different), and the two `negative' classes (same/different and different/same). We see noteworthy variation in model performance across these classes: where there is little or no training data, accuracy is high for the `negative' classes and low for the `positive' ones. This pattern stabilizes quickly, and then we find that the different/different class is persistently the most difficult, which aligns with general qualitative findings from behavioral experiments. \Figref{fig:premack-by-class} depicts these findings for our best model.

\section{General Discussion}

Equality is a key case study for understanding the origins of human relational reasoning. This case study has been puzzling for symbolic accounts of reasoning because such accounts do not provide a compelling explanation for why some equality tasks are so easy to learn and others are so hard. In addition, evidence of graded learning and generalization in non-human species suggests that a gradual learning account might provide more traction in explaining the empirical data \citep{wasserman:2017}. Inspired by this work, we revisited a long-standing debate about whether neural network models can learn equality relations from data \citep{alhama:2019}.

Our work here makes three contributions to this debate. First, we show that non-featural representations -- both random and pretrained -- allow standard neural networks to learn simple, sequential, and hierarchical equality tasks. Both the research that originated this debate \citep{marcus:1999,marcus:2001,dienes:1999,seidenberg:1999a,seidenberg:1999b,elman:1999,negishi:1999} and more recent work \citep{weyde2019, weyde2018, kopparti2020, alhama2018} only involve experiments where featural representations are used. We suggest that this choice led directly to the negative conclusions from this body of work. Second, we show that neural networks can achieve high test accuracy on the sequential equality task with no negative feedback, suggesting that a negative feedback learning regime is not critical for learning equality. Finally, we show that a neural network trained only on simple equality can generalize to hierarchical equality, even in a ``zero-shot'' evaluation. Although pretrained representations sometimes led to faster learning, they were not a necessary component for models to succeed, and success was possible even using random representations.

\subsection{The implications of pretraining}

In some settings, our current models require many more training instances than humans seem to need. However, our pretraining approach suggests a path forward: by using pretrained models as modular components, we can get traction on challenging tasks without any training specifically for those tasks. In some cases, even a small amount of additional training can make a substantial difference.

One implication of our pretraining findings is that it should be possible to scaffold non-human animals' performance in complex, hierarchical equality tasks via training on simpler ones. Indeed, \citet{smirnova2015} show just this result in crows, consistent with our findings. Although we do not discount the potential role of linguistic labels in informing adult humans' expertise in such tasks \citep{gentner:2003}, pretraining also provides a potential account of how infants and young children might succeed in a range of equality reasoning tasks without access to specific linguistic symbols like ``same'' \citep{walker:2016,ferry:2015,hochmann2016}.

While pretraining in the sparse, artificial contexts of our models is far from accurately capturing the experience of infants and other animals, we believe it is reasonable to think of cognitive systems as “pretrained” by their perceptual experiences and by their evolved perceptual architecture. This “pretraining” might lead them to have continuous representations of perceptual information that are non-featural in the sense of our models, but which still encode psychologically meaningful properties. In this sense, human generalizations could be similar to those made by our models in that both encode meaningful properties of stimuli in a way that is not perfectly individuated or discrete. Further, both can make rapid (and sometimes one-shot) generalizations, especially in cases where the agent has had prior experience with the stimuli \citep{rabagliati:2019}. This kind of viewpoint on our pretraining simulations is consistent with a range of views of how complex human abilities are created from simpler one \citep[e.g.,][]{frank2008,heyes2018}.

We have not offered a theory of how an agent might come to be able to combine pretrained components to solve more complex tasks, however. Rather, we simply pieced these components together by hand to achieve our desired outcomes. A natural next step would be to learn how to effectively combine these modular pieces. The artificial intelligence literature currently offers a range of techniques that could be used for this purpose, including Neural Module Networks \citep{Andreas-etal:2016}, Compositional Recursive Learners \citep{chang2018automatically}, Modular Networks \citep{Kirsch-etal:2018}, and Recursive Routing Networks \citep{Cases-etal:2019}. These techniques might provide a fruitful avenue for simulating the emergence of more complex cognitive abilities.

\subsection{Beyond exact equality}

We have so far confined our discussion to idealized notions of \emph{same} and \emph{different} that are defined in terms of complete mathematical identity. These are the terms of the original debate involving \citet{marcus:1999}, \citet{dienes:1999}, \citet{seidenberg:1999a,seidenberg:1999b}, \citet{elman:1999}, \citet{negishi:1999}, and others. We hope to have established that neural networks can solve this version of the problem. However, the cognitive notions of \emph{same} and \emph{different} are richer and more multifaceted than this.

Our models and findings hold for the case where judgments are made about one and the same image, but it is an open question how to extend them to situations in which one has two distinct images of the same entity and the intended label is ``same''. Even this basic expansion of the problem space poses many challenging new questions concerning context dependence (e.g., when are two different apples of the same type judged to be ``the same'') and human fallibility (one could fail to perceive relevant differences or fail to ignore irrelevant ones), and thus the very notion of success is also likely to become more graded and context dependent. \citet{webb2021emergent} begin to explore this problem, and those initial results give us confidence that the kinds of networks we propose here could be conditioned contextually to provide flexible, context-sensitive interpretations for sameness and graded similarity \citep{medin1993}, holding the promise of unifying models of identity, similarity, and related notions.

More broadly still, our work suggests a possible way forward in understanding the acquisition of logical semantics. Graded logical functions like those our models learned here could form the foundation for a semantics of words like ``same'' \citep{potts2019}. Such an option is appealing because it escapes from the circularity of defining the semantics of linguistic symbols as originating in a mental primitive {\sc same}. A semantics for ``same'' requires defining its inputs and outputs as well as how it composes with other symbols. Further, understanding the pragmatics of ``same'' then requires understanding how exact the similarity must be for the statement to be true in particular contexts.

\subsection{Conclusions}

Even the best present-day deep learning models often fail to achieve systematic and general solutions \citep{Lake2018, Marcus2018,geiger2019,Hupkes2020,linzen2020,wu2021}. However, as our experiments demonstrate, abstract equality reasoning is too simple of a domain to expose this failure. Indeed, at this point, even very complicated problems in logical semantics might not suffice to make this point, given the high level of performance that can sometimes be achieved \citep{Bowman:Potts:Manning:2015,mul2019siamese}.

Earlier debates about the nature of equality computations centered around the question of whether models included explicitly symbolic elements. We believe ours do not; but it is of course possible to quibble with this judgment. For example, since the supervisory signals used in Experiments 1 and 3 are generated based on a symbolic rule, perhaps that makes these models symbolic under some definition. (Of course, the same argument could be applied to the supervision signal that is provided to crows, baboons, and human children in some tasks).

This kind of argument increasingly seems terminological, rather than substantive, however. Neural models may learn symbolic computations in ways that do not contain explicit operators but that nevertheless have elements that play the same causal role. \citet{geiger2020} and \citet{geiger2021} perform causal abstraction analyses of trained neural models and find that they define and use symbolic variables at an abstract level of computation. In related work, \citet{Geiger:Wu:Lu-etal:2021} train neural models to implement abstract symbolic computations in order to solve systematic generalization tasks. These techniques leverage recent innovations in models of causality and abstraction \citep{chalupka16,rubenstein17,beckers2019}, and they provide more evidence for the classic view that neural networks are capable of implementing symbolic computations \citep{smolensky1988,fodor1988} which has received recent focus again  \citet{Piantadosi:2021,Deepmind:2021}. So an advocate for a symbolic view could even say that such networks (and likely ours as well) have learned symbols, though this move might lead to more confusion than clarity with respect to the original debate.

In the end, the primary goal is not to resolve the question of whether explicit symbolic representations are necessary (although by most reasonable definitions we believe we have presented a negative answer to that question). Rather, the hope is to create an explicit learning theory for relational reasoning, which might in turn explain the rich and puzzling empirical landscape \citep{carstensen:inpress}. Our hope is that -- by providing a range of architectures that learn equality functions -- the work described here takes a first step in this direction.

\bibliographystyle{acl_natbib}


\section{Introduction}\label{sec:introduction}
In recent years, the interest in combinatorial games as a challenge in AI has increased after the first AlphaGo program~\cite{silver2016mastering}  defeated the human world champion of Go~\cite{plaat2020learning}. The great success of the AlphaGo and AlphaZero programs~\cite{silver2016mastering,silver2017mastering,silver2018general} in two-player games, has inspired attempts in other domains~\cite{segler2018planning,wang2020warm}. So far, one of the most challenging single player games, Morpion Solitaire~\cite{cboyer2020} has not yet been studied with this promising deep reinforcement learning approach.

Morpion Solitaire is a popular single player game since 1960s~\cite{cboyer2020,demaine2006morpion}, because of its simple rules and simple equipment, requiring only  paper and  pencil. Due to its large state space it is also an interesting AI challenge in single player games, just like the game of Go challenge in two-player turn-based games. Could the AlphaZero self-play approach, so successful in Go, also work in Morpion Solitaire? For ten years little progress has been made in Morpion Solitaire. It is time to take up the challenge and to see if a self-play deep reinforcement learning approach will work in this challenging game.

AlphaGo and AlphaZero combine deep neural networks~\cite{schmidhuber2015deep} and Monte Carlo Tree Search~(MCTS)~\cite{browne2012survey} in a self-play framework that learns by curriculum learning~\cite{bengio2009curriculum}. Unfortunately, these approaches can not be directly used to play single agent combinatorial games, such as travelling salesman problems~(TSP)~\cite{rego2011traveling} and bin package problems~(BPP)~\cite{hu2018multi}, where cost minimization is the goal of the game. To apply self-play for single player games, Laterre et al. proposed a Ranked Reward~(R2) algorithm. R2 creates a relative performance metric by means of ranking the rewards obtained by a single agent over multiple games. In two-dimensional and three-dimensional bin packing R2 is reported to out-perform MCTS~\cite{laterre2018ranked}. In this paper we use this idea for Morpion Solitaire. Our contributions can be summarized as follows:
\begin{enumerate}
    \item We present the first implementation\footnote{Source code: https://github.com/wh1992v/R2RRMopionSolitaire} of Ranked Reward AlphaZero-style self-play for Morpion Solitaire.
    \item On this implementation, we report our current best solution, of 67 steps~(see Fig~\ref{fig:67stepsgrid}).
\end{enumerate}
This result is very close to the human record, and shows the potential of the self-play reinforcement learning approach in Morpion Solitaire, and other hard single player combinatorial problems.

This paper is structured as follows.
After giving an overview of related work in Sect.\,\ref{sec:relatedwork}, we introduce the
Morpion Solitaire challenge in Sect.\,\ref{sec:morpion}. Then we present how to integrate the idea of R2 into  AlphaZero self-play in Sect.\,\ref{sec:R2}. Thereafter, we set up the experiment in Sect.\,\ref{sec:setup}, and show the result and analysis in Sect.\,\ref{sec:result}. Finally, we conclude our paper and discuss future work.

\section{Related Work}\label{sec:relatedwork}
Deep reinforcement learning~\cite{mnih2015human} approaches, especially the AlphaGo and AlphaZero programs, which combine online tree search and offline neural network training, achieve super human level of playing two player turn-based board games such as Go, Chess and Shogi~\cite{silver2016mastering,silver2017mastering,silver2018general}. These  successes spark the interest of creating new deep reinforcement learning approaches to solve  problems in the field of game AI, especially for other two player games~\cite{tian2019elf,wang2020analysis,wang2018monte,wang2018assessing}.

However, for single player games, self-play deep reinforcement learning approaches are not yet well studied since the approaches used for two-player games can not directly be used in single player games~\cite{laterre2018ranked}, since the goal of the task changes from winning from an opponent, to minimizing the solution cost. Nevertheless, some researchers did initial works on single games with self-play deep reinforcement learning~\cite{moerland2018a0c}. The main difficulty is representing single player games in ways that allow the use of a deep reinforcement learning approach. In order to solve this difficulty, Vinyals et al.~\cite{vinyals2015pointer} proposed a neural architecture~(Pointer Networks) to represent combinatorial optimization problems as sequence-to-sequence
learning problems. Early Pointer Networks achieved decent performance on TSP, but this approach is computationally expensive and  requires handcrafted training examples for supervised learning methods. Replacing supervised learning methods by actor-critic methods removed this requirement~\cite{bello2016neural}. In addition, Laterre et al.\ proposed the R2 algorithm through ranking the rewards obtained by a single agent over multiple games to label win or loss for each search, and this algorithm reportedly outperformed plain MCTS in the bin packing problem (BPP)~\cite{laterre2018ranked}. Feng et al.\ recently used curriculum-driven deep reinforcement learning to solve hard Sokoban instances \cite{feng2020solving}.

In addition to TSP and BPP, Morpion Solitaire has long been a  challenge in NP-hard single player problems. Previous works on Morpion Solitaire mainly employ traditional heuristic search algorithms~\cite{cboyer2020}. Cazenave created Nested Monte-Carlo Search and found an 80 moves record~\cite{cazenave2009nested}. After that, a new Nested Rollout Policy Adaptation algorithm achieved a new 82 steps record~\cite{rosin2011nested}. Thereafter, Cazenave applied Beam Nested Rollout Policy Adaptation~\cite{cazenave2012beam}, which reached the same 82 steps record but did not exceed it, indicating the difficulty of making further progress on Morpion Solitaire using traditional search heuristics.

We believe that it is time for a new approach, applying (self-play) deep reinforcement learning  to train a Morpion Solitaire player. The combination of the R2 algorithm with the AlphaZero self-play framework could be a first alternative for above mentioned approaches.

\section{Morpion Solitaire}\label{sec:morpion}
Morpion Solitaire is a single player game played on an unlimited grid. It is a well know NP-hard challenge~\cite{cboyer2020}. The rules of the game are simple. There are 36 black circles as the initial state~(see Fig~\ref{fig:ruleexample}). A move for Morpion Solitaire consists of two parts: a) placing a new circle on the paper so that this new circle can be connected with four other existing circles horizontally, vertically or diagonally, and then b) drawing a line to connect these five circles~(see action 1, 2, 3 in the figure). A line is allowed to cross over each other~(action 4), but not
allowed to overlap. There are two versions: the Touching~(5T) version and the Disjoint~(5D) version. For the 5T version, it is allowed to touch~(action 5, green circle and green line), but for the 5D version, touching is illegal~(any circle can not belong to two lines that have the same direction). After  a legal action the circle and the line are added to the grid. In this paper we are interested in the 5D version.

The best human
score for the 5D version is 68 moves \cite{demaine2006morpion}. A score of 80 moves was found by means of Nested Monte-Carlo search~\cite{cazenave2009nested}. In addition,~\cite{rosin2011nested} found a new record with 82 steps, and \cite{cazenave2012beam} also found a 82 steps solution. It has been proven mathematically  that the 5D version has an upper bound of 121~\cite{kawamura2013morpion}.

\begin{figure}[htbp]
\centerline{\includegraphics[width=0.9\columnwidth]{ruleexample.pdf}}
\caption{Moves Example: Moves 1, 2, 3, 4 are legal moves, move 5 is illegal for the 5D version, but legal for the 5T version.}
\label{fig:ruleexample}
\end{figure}

\section{Ranked Reward Reinforcement Learning}\label{sec:R2}
AlphaZero self-play achieved milestone successes in  two-player games, but  can not be directly used for single player cost minimization games. Therefore, the R2 algorithm has been  created to use self-play
for generic single player MDPs. R2 reshapes the rewards according to player's relative performance over recent games~\cite{laterre2018ranked}. The pseudo code of  R2  is given in Algorithm~\ref{alg:r2a0g}.

\begin{algorithm*}[bth!]
\caption{Ranked Reward Reinforcement Learning within AlphaZero-like Self-play Framework}
\label{alg:r2a0g}
\begin{algorithmic}[1]
\footnotesize
\Function{RankedRewardReinforcementLearning}{}
\State Initialize $f_\theta$ with random weights; Initialize retrain buffer $D$ and  reward list $B$
\For{iteration=1, $\dots$ $\dots$, $I$}
\Comment self-play curriculum of $I$ tournaments
\For{episode=1,$\dots$, $E$}\Comment{stage 1,
self-play tournament of $E$ games}
\For{t=1, $\dots$, $T^\prime$, $\dots$, $T$}
\Comment play game of $T$ moves

\State$\pi_{t} \leftarrow$ perform MCTS based on  $f_\theta$ or directly get policy from  $f_\theta$
\Comment with or without tree search enhancement \label{mctsenhancement}
\State $a_t=$randomly select on $\pi_t$ before $T^\prime$ or $\arg\max_a(\pi_t)$ after $T^\prime$ step
\State executeAction($s_t$, $a_t$)
\EndFor

\State Calculate game reward $r_{T}$ and store it in $B$\label{line:calreward}
\State Calculate threshold $r_\alpha$ based on the recent games rewards in $B$

\State Reshape the ranked reward $z$ following Equation~\ref{equ:reshape}\label{line:reshape}\Comment{Ranked Reward}

\State Store every $(s_t,\pi_t,z_t)$ with ranked rewards $z_t$ ~($t\in[1,T]$) in $D$
\EndFor
\State Randomly sample  minibatch of examples~($s_j$, $\pi_j$, $z_j$) from $D$ \Comment{stage 2}
\State Train $f_{\theta^\prime}\leftarrow f_\theta$
\State Play once with MCTS enhancement on $f_{\theta^\prime}$\label{mctsplay} \Comment{stage 3}
\State Replace $f_{\theta}\leftarrow f_\theta^\prime$

\EndFor
\State \Return $f_\theta$;
\EndFunction
\end{algorithmic}
\end{algorithm*}

Following  AlphaZero-like self-play~\cite{wang2019alternative}, we demonstrate the typical three stages as shown in the pseudo code. For self-play in Morpion Solitaire MCTS  is too time consuming due to the large state space. Thus, we rely on the policy directly from $f_\theta$ without tree search~(line~\ref{mctsenhancement}). For stage 3, we directly replace the previous neural network model with the newly trained model. and we let the newly trained model play a single time with MCTS enhancement~(line~\ref{mctsplay}).  The R2 idea is integrated~(see line~\ref{line:calreward} to line~\ref{line:reshape}). The reward list $B$ stores the recent game rewards. According to a ratio $\alpha$, the threshold of $r_\alpha$ is calculated. We then compare  $r_\alpha$ to the game reward $r_T$ to reshape the ranked reward $z$ according to Equation~\ref{equ:reshape}.

\begin{equation}\label{equ:reshape}
    z=
\begin{cases}
1& r_T > r_\alpha\\
-1& r_T < r_\alpha\\
random(1, -1) & r_T = r_\alpha
\end{cases}
\end{equation}
where $r_\alpha$ is the stored reward value in $B$ indexed by $L\times \alpha$, $L$ is the length of $B$, $\alpha$ is a ratio parameter.

\section{Experiment Setup}\label{sec:setup}
We perform our experiments on a GPU server with 128G RAM, 3TB local storage, 20 Intel Xeon E5-2650v3 cores~(2.30GHz, 40 threads), 2 NVIDIA Titanium GPUs~(each with 12GB memory) and 6 NVIDIA GTX 980 Ti GPUs~(each with 6GB memory).

The hyper-parameters of our current R2 implementation are as much as possible equal to previous work. In this work, all neural network models share the same structure as in~\cite{wang2019alternative}. The hyper-parameter values for Algorithm~\ref{alg:r2a0g} used in our experiments are given in Table~\ref{defaulttab}. Partly, these  values are set based on the work reported in~\cite{wang2019hyper} and the R2 approach for BPP~\cite{laterre2018ranked}. $T'$ is set to half of the current best record. $m$ is set to 100 if using MCTS in self-play, but 20000 for MCTS in stage 3. Furthermore, as there is an upper bound of the best score~(121), we did experiments on 16$\times$16, 20$\times$20 and 22$\times$22 boards respectively. Training time for every algorithm is about a week.

\begin{table}[!bth]
\small
\centering
\caption{Default Parameter Settings}\smallskip
\resizebox{1\columnwidth}{!}{
\smallskip\begin{tabular}{|c|c|c|}
\hline
Parameter	& Brief Description& Default Value\\
\hline
\emph{I}	&number of iterations 	&100	\\
\hline
\emph{E}    &number of episodes   &50\\
\hline
\emph{T'}	&step threshold	&41\\
\hline
\emph{m}	&MCTS simulation times &20000\\
\hline
\emph{c}    &weight in UCT  &1.0\\
\hline
\emph{rs}	& number of retrain iterations &10\\
\hline
\emph{ep}	& number of epochs	&5	\\
\hline
\emph{bs}	& batch size	&64\\
\hline
\emph{lr}	& learning rate	&0.005\\
\hline
\emph{d}    & dropout probability  &0.3\\
\hline
\emph{L}    & length of $B$ &200\\
\hline
\emph{$\alpha$}	& ratio to compute $r_\alpha$	&0.75 \\
\hline
\end{tabular}
}
\label{defaulttab}
\end{table}

\section{Result and analysis}\label{sec:result}

As we mentioned above, the best score for Morpion Solitaire of 82 steps has been achieved by Nested Rollout Policy Adaptation in 2010. The best score achieved by human is 68. Our first attempt with limited computation resources on a large size board~(22$\times$22) achieved a score of 67, very close to the best human score. The resulting solution is  shown in Fig~\ref{fig:67stepsgrid}.

Based on these promising results with  Ranked Reward Reinforcement Learning we identify  areas for further improvement. First,  parameter values for the Morpion Solitaire game can be fine-tuned using results of small board games. Especially the parameter  $m=100$ seems not sufficient for large boards. Second, the neural network could be changed to Pointer Networks and the size of neural network should be deeper.

Note that the tuning of parameters is critical; if the reward list $B$ is too small,  the reward list can be easily filled up by scores close to 67. The training will then be stuck in a locally optimal solution. As good solutions are expected to be sparsely distributed over the  search space, this increases the difficulty to get rid of a locally optimal solution once the algorithm has focused on it.

\begin{figure}[htbp]
\centerline{\includegraphics[width=0.9\columnwidth]{67steps.pdf}}
\caption{Detailed Steps of Our Best Solution}
\label{fig:67stepsgrid}
\end{figure}

\section{Conclusion and Outlook}\label{sec:conclusion}
In this work, we apply a Ranked Reward Reinforcement Learning AlphaZero-like approach to play Morpion Solitaire,  an important NP-hard  single player game challenge. We train the player on 16$\times$16, 20$\times$20 and 22$\times$22 boards, and find a near best human performance solution with 67 steps.  As a first attempt of utilizing self-play deep reinforcement learning approach to tackle Morpion Solitaire, achieving near-human performance is a promising result.

Our first results give us reason to believe that there remain ample possibilities to improve the approach by investigating the following aspects:
\begin{enumerate}
    \item Parameter tuning: such as the Monte Carlo simulation times. Since good solutions are  sparse in this game, maybe more exploration is beneficial?
    \item Neural Network Design: It is reported that Pointer Networks perform better on combinatorial problems. A next step could be to also make the neural network structure deeper.
    \item Local Optima: Through monitoring the reward list $B$, we can adjust in time by enlarging more exploration once it gets stuck in a locally optimal solution.
    \item Computation resources and parallelization: enhanced parallelization may improve the results.
\end{enumerate}

To summarize, although the problem is difficult due to its large state space and sparsity of good solutions, applying a Ranked Reward self-play Reinforcement Learning approach to tackle Morpion Solitaire is a promising and learns from \textit{tabula rasa}.  We present our promising near-human result to stimulate future work on Morpion Solitaire and other single agent games with self-play reinforcement learning.

\section*{Acknowledgment}

Hui Wang acknowledges financial support from the China Scholarship Council (CSC), CSC No.201706990015.

\bibliographystyle{./IEEEtran}