{'fraction_non_alphanumeric': 0.03189208156263402, 'fraction_numerical': 0.013216889547350773, 'mean_word_length': 4.952502514117738, 'pattern_counts': {'":': 0, '<': 8, '<?xml version=': 0, '>': 7, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 7, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Relational reasoning and generalization using non-symbolic neural networks

The notion of equality (identity) is simple and ubiquitous, making it a key case study for broader questions about the representations supporting abstract relational reasoning. Previous work suggested that neural networks were not suitable models of human relational reasoning because they could not represent mathematically identity, the most basic form of equality. We revisit this question. In our experiments, we assess out-of-sample generalization of equality using both arbitrary representations and representations that have been pretrained on separate tasks to imbue them with structure. We find neural networks are able to learn (1) basic equality (mathematical identity), (2) sequential equality problems (learning ABA-patterned sequences) with only positive training instances, and (3) a complex, hierarchical equality problem with only basic equality training instances ("zero-shot'"generalization). In the two latter cases, our models perform tasks proposed in previous work to demarcate human-unique symbolic abilities. These results suggest that essential aspects of symbolic reasoning can emerge from data-driven, non-symbolic learning processes.


Introduction
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 (e.g., Gentner & Goldin-Meadow, 2003). By far the most common case study of abstract relations has been equality. 1 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 same pair, AA, must be matched to a novel same pair, BB (KR Thompson, Rattermann, & L Oden, 2001;Premack, 1983). Preschool children also struggle to learn these regularities in a seemingly similar task (Walker, Bridgers, & Gopnik, 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 (Avarguès-Weber, Deisig, & Giurfa, 2011;Giurfa, Zhang, Jenett, Menzel, & Srinivasan, 2001), and human infants can generalize identity patterns (Anderson, Chang, Hespos, & Gentner, 2018) and succeed in relational matching tasks (Ferry, Hespos, & Gentner, 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 (Carstensen & Frank, 2021).
The learning task in all of these cases can be described using the predicate same (or equivalently, =), which operates over two inputs and returns true if they are identical in some respect, else 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 (Marcus, Vijayan, Rao, & Vishton, 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 (Gervain, Berent, & Werker, 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 (e.g., Frank & Tenenbaum, 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 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 (Wasserman, Castro, & Fagot, 2017). This view acknowledges the increasing evidence that other species like pigeons (Cook & Wasserman, 2007), crows (Smirnova, Zorina, Obozova, & Wasserman, 2015), and baboons (Fagot & Thompson, 2011) can make true, out-of-sample generalizations of same and 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 (e.g., Castro, Kennedy, & Wasserman, 2010). 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 (e.g., LeCun, Bengio, & Hinton, 2015;Saxe, McClelland, & Ganguli, 2019).
In an influential rebuttal of the use of neural network models for capturing relational reasoning, Marcus et al. (1999) argued that a broad class of recurrent neural networks were unable to learn a general solution to sequential equality problems and Marcus (2001) argued that feed-forward neural networks are even unable to learn a general solution even to mathematical identity, which is arguably the simplest version of same/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) Marcus et al.'s equality tasks (Dienes, Altmann, & Gao, 1999;Elman, 1999;Negishi, 1999;Seidenberg & Elman, 1999a, 1999b), yet these examples were controversial. The resulting debate (reviewed in Alhama & Zuidema, 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 (Bowman, Angeli, Potts, & Manning, 2015;Williams, Nangia, & Bowman, 2018), question answering (Rajpurkar, Jia, & Liang, 2018;Rajpurkar, Zhang, Lopyrev, & Liang, 2016), and visual reasoning (Johnson et al., 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 (Alhama & Zuidema, 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 (Alhama & Zuidema, 2018;Kopparti & Weyde, 2020;Weyde & Kopparti, 2018. Further, though tasks and contexts vary, work in both computer vision (Fleuret et al., 2011;Gülçehre & Bengio, 2016;Kim, Ricci, & Serre, 2018) and machine reasoning (Palm, Paquet, & Winther, 2018;Raposo et al., 2017;Santoro et al., 2018Santoro et al., , 2017  and sometimes equality-based reasoning specifically -is difficult or impossible in standard network architectures. 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 (Collobert et al., 2011;Devlin, Chang, Lee, & Toutanova, 2019;Mikolov, Sutskever, Chen, Corrado, & Dean, 2013;Pennington, Socher, & Manning, 2014;Peters et al., 2018). The use of pretrained representations to solve downstream tasks in particular is argued to be a hallmark of natural learning systems (Zador, 2019), has been an important feature of historical models from cognitive science (e.g., Landauer & Dumais, 1997;McRae & Hetherington, 1993), and is essential in the latest wave of state-of-the-art natural language processing models (T. Brown et al., 2020;Devlin et al., 2019;Liu et al., 2019;Radford et al., 2019).
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 ( Figure 1): (1) learning to discriminate pairs of objects that exemplify the relation same or different, (2) learning sequences with repeated same elements , and (3) learning to distinguish hierarchical same and different relations in a context with pairs of pairs exemplifying these relations (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. Marcus et al. (1999) and 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 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 (Kopparti & Weyde, 2020;Weyde & Kopparti, 2018. 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 (e.g., Marcus, 1999), 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.
In all our experiments, we define same and 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 (Wang & Deng, 2021). Thus, following the protocols of Marcus et al. (1999) and 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.

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. 2

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 Goodfellow, Bengio, and Courville 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: systematic generalization tasks and 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 Lake and Baroni (2018), Wu, Kreiss, Ong, and Potts (2021) define test sets around specific adjective-noun modification structures A N , ensuring that the training set includes only examples involving A N and A N for A = A and N = N . Given a general assumption of systematicity (Fodor & Pylyshyn, 1988), we expect this training set to support learning to make accurate predictions for A N , and the design of the train-test split gives us confidence that such predictions are not based on mere memorization of A N itself. For other examples involving systematic generalization tests, see Geiger, Richardson, and Potts 2020;Goodwin, Sinha, and O'Donnell 2020;Hupkes, Dankers, Mul, and Bruni 2020;Yanaka, Mineshima, Bekki, and Inui 2020. In adversarial testing (sometimes called 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 Winograd (1972) (see also Levesque 2013), and it has been used effectively in a number of domains, including object recognition in digital images (Goodfellow, Shlens, & Szegedy, 2015), basic factual question answering (Jia & Liang, 2017), and natural language inference (Glockner, Shwartz, & Goldberg, 2018;Nie, Wang, & Bansal, 2019). More recently, adversarial testing has been extended to include training on adversarial examples in order to develop more robust models (Bartolo, Roberts, Welbl, Riedel, & Stenetorp, 2020;Kiela et al., 2021;Nie et al., 2020;Potts, Wu, Geiger, & Kiela, 2021).
In our work, we adopt elements of both these modes for assessing generalization. Following Marcus et al. (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 (α, α) and (α, β) 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.

Representations
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 featural representations and 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.    We ground our discussion in a hypothetical universe of blocks which vary by shape and color. Figure  Featural representations. The defining characteristic of 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 localist for the special case of featural representations in which only objects are represented and there is a feature corresponding to each object. In Figure 2b, 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.
representations; as discussed below, here we define these terms specifically to refer to representations whose features correspond to specific entities. Figure 3 . 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.
We will refer to featural representations that are not localist as 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 Figure 2c. 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.
Non-featural representations. A non-featural representation is a vector that encodes property values implicitly across many dimensions. Perhaps the simplest non-featural representations are completely random vectors, as in Figure 2d. 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.
Pretraining. Random representations are a starting point that encodes object identity, but we can pretrain these representations via a learning process, imbuing them with rich structure that implicitly encodes property values across many dimensions. Figure 2e provides a simple example. This matrix is the results of pretraining the representations in Figure 2d 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 Figure 2f have no such structure, while the pretrained representations in Figure 2g 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: Here, E[i] is the vector representation for example i in an embedding matrix E of dimension |V | × 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×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 (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 j hy and bias b j y . Each of these again defines a linear projection, now of h i . The result is fed through the softmax activation function: 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.
Figure 3 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 j hy and b j y 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: where y i,j,k is the correct label for example i in task j and h θ (i) j,k is the predicted value for example i in task j. We use θ to abbreviate all the model parameters: E, W xh , b h , and W j hy and b j y 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.
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 entities unseen during training, while binary feature representations prevent generalization to 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. 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 (Kopparti & Weyde, 2020;Weyde & Kopparti, 2018 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.

Experiment 1: A feed-forward neural model of same-different relations
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.

Methods
Our basic model for equality is a feed-forward neural network with a single hidden representation layer. The model is depicted graphically in Figure 4a and defined as follows: 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 × 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 × 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 The single layer network computing equality from the first experiment.
The recurrent LSTM network producing ABA sequences from the second experiment.
ReLU y softmax (c) The two layer network computing hierarchical equality from the third experiment.
x 1 x 2 The single layer network pretrained on equality computing hierarchical equality from the fourth experiment.
where θ 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 θ (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: 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 (Pedregosa et al., 2011), 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. Figure 5 shows our results, for a model with an embedding dimension of 10 and a hidden-layer dimension of 100. (In the Appendix, Figure D1 provides results for other network dimensionalities, and Figure D7a 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 Figure 2, 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. Mean accuracy (20 runs) no pretraining 3-task pretraining 5-task pretraining 10-task pretraining Figure 5 . 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.

Results
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.

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.

Experiment 2: A recurrent neural model of sequential same-different
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 (e.g., Marcus, 1999). While this argument likely holds true for language learning (in which supervision is generally agreed not to be binary or direct; R. Brown & Hanlon, 1970;Chouinard & Clark, 2003), it is not necessarily true for learning more generally. Nevertheless, learning of sequential rules without negative feedback is possible for infants Rabagliati, Ferguson, & Lew-Williams, 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.

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 (Hochreiter & Schmidhuber, 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: This holds for t > 0, and we set h 0 = 0. LSTM is a long short-term memory cell (Hochreiter & Schmidhuber, 1997). We visualize this model in Figure 4b. The input is a sequence of vectors x 1 , x 2 , x 3 , . . . , 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 LSTM cell along with the previous hidden representation h t−1 . The defining feature of an 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 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 × 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: Mean accuracy (20 runs) no pretraining 3-task pretraining 5-task pretraining 10-task pretraining Figure 6 . 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.
for N examples. Here, T i is the length of example i. As before, θ abbreviates the parameters of the model as specified in (8)-(9). We use h θ (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 (Paszke et al., 2019). 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 <s> a b a </s>, where b = 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 <s> x where 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 y x </s>, where y is any character (from the training or assessment vocabulary) except x. In our experiments, we use a test vocabulary of 26 items, which creates 52 distinct y x </s> continuations and hence 52 distinct test examples. Figure 6 shows our results, for networks with 2-dimensional embeddings and 100dimensional hidden representations. (Figure D2 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. Figure D7b provides training-set results that are comparable to those in Figure 6. 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.

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.

Experiment 3: A feed-forward neural model of hierarchical same-different relations
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 Premack (1983) is an interesting test case: given a pair of pairs ((a, b), (c, d) Premack suggested that the ability exemplified by this task -reasoning about hierarchical same and 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.

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 Figure D3). 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 Figure 4c and we define 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).

Figure 7a
shows our results for networks with 10-dimensional embeddings and 100dimensional hidden layers. ( Figure D4 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.

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 (e.g., Endress, Scholl, & Mehler, 2005;Marcus et al., 1999). 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.

Experiment 4: A tree-structured model of hierarchical same-different relations pretrained on simple equality
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 Thompson, Oden, and Boysen (1997), in which chimpanzees that received pretraining on a basic equality (same/different judgment) task -but not naive champanzees -succeed in a hierarchical equality task. Mean accuracy (20 runs) no pretraining 3-task pretraining 5-task pretraining 10-task pretraining (a) Experiment 3 results: feed-forward neural networks with two hidden layers trained on our hierarchical equality task (10-dimensional inputs; 100-dimensional hidden layers). Mean accuracy (20 runs) no pretraining 3-task pretraining 5-task pretraining 10-task pretraining (b) 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. Figure 7 . 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.

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 Figure 4d and defined as follows: Here, W xh , W hy , b h , and b y are the parameters from the model in equations (4)-(5) 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. 4 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. Figure 7b shows our results for networks with 25-dimensional inputs, which sets the dimensionality of the hidden representations to 50. (See Figure D4 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 Figure D7d, we provide comparable training set assessments; in that context, pretraining has the opposite effect, slightly slowing down learning.)

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. Figure D6 depicts these findings for our best model.

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 4 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 (Andreas, Rohrbach, Darrell, & Klein, 2016;Cases et al., 2019;Chang, Gupta, Levine, & Griffiths, 2019;Kirsch, Kunze, & Barber, 2018). We briefly return to this point in our 'General discussion' below.
non-human species suggests that a gradual learning account might provide more traction in explaining the empirical data (Wasserman et al., 2017). Inspired by this work, we revisited a long-standing debate about whether neural network models can learn equality relations from data (Alhama & Zuidema, 2019).
Our work here makes three contributions to this debate. First, we show that nonfeatural representations -both random and pretrained -allow standard neural networks to learn simple, sequential, and hierarchical equality tasks. Both the research that originated this debate (Dienes et al., 1999;Elman, 1999;Marcus, 2001;Marcus et al., 1999;Negishi, 1999;Seidenberg & Elman, 1999a, 1999b) and more recent work (Alhama & Zuidema, 2018;Kopparti & Weyde, 2020;Weyde & Kopparti, 2018 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.

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, Smirnova et al. (2015) 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 (Gentner & Goldin-Meadow, 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" (Ferry et al., 2015;Hochmann, Mody, & Carey, 2016;Walker et al., 2016).
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 (Rabagliati et al., 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 (e.g., Frank, Everett, Fedorenko, & Gibson, 2008;Heyes, 2018).
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 (Andreas et al., 2016), Compositional Recursive Learners , Modular Networks (Kirsch et al., 2018), and Recursive Routing Networks (Cases et al., 2019). These techniques might provide a fruitful avenue for simulating the emergence of more complex cognitive abilities.

Beyond exact equality
We have so far confined our discussion to idealized notions of same and different that are defined in terms of complete mathematical identity. These are the terms of the original debate involving Marcus et al. (1999), Dienes et al. (1999), Elman (1999a, 1999b), Elman (1999), Negishi (1999), and others. We hope to have established that neural networks can solve this version of the problem. However, the cognitive notions of same and 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. Webb, Sinha, and Cohen (2021) 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 (Medin, Goldstone, & Gentner, 1993), 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" (Potts, 2019). Such an option is appealing because it escapes from the circularity of defining the semantics of linguistic symbols as originating in a mental primitive 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.

Conclusions
Even the best present-day deep learning models often fail to achieve systematic and general solutions (Geiger, Cases, Karttunen, & Potts, 2019;Hupkes et al., 2020;Lake & Baroni, 2018;Linzen, 2020;Marcus, 2018;Wu et al., 2021). 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 Mul & Zuidema, 2019).
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. Geiger et al. (2020) and 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, Geiger, Wu, et al. (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 (Beckers & Halpern, 2019;Chalupka, Eberhardt, & Perona, 2016;Rubenstein et al., 2017), and they provide more evidence for the classic view that neural networks are capable of implementing symbolic computations (Fodor & Pylyshyn, 1988;Smolensky, 1986) which has received recent focus again Piantadosi (2021);Santoro, Lampinen, Mathewson, Lillicrap, and Raposo (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 (Carstensen & Frank, 2021). 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.

Appendix A Model optimization details
The feed forward networks for basic and hierarchical equality were implemented using the multi-layer perception from scikit-learn and a cross entropy function was used to compute the prediction error. The recurrent LSTM network for the sequential ABA task was implemented using PyTorch and a mean squared error function was used to compute the prediction error. The networks for pretraining representations and for the hierarchical equality task were also implemented using PyTorch, with cross-entropy loss functions used to compute the prediction errors.
For all models, Adam optimizers (Kingma & Ba, 2014) were used. For all models, we used a batch size of 1 and ran a hyperparameter search over learning rate values of {0.00001, 0.0001, 0.001} and l2 normalization values of {0.0001, 0.001, 0.01} for each hidden dimension and input dimension. We considered hidden dimensions of {2, 10, 25, 50, 100} and input dimensions of {2, 10, 25, 50, 100}. In the main text, we graph results for the single best hyperparameter setting, averaged over 20 runs with different random model and input intializations. See 'Additional results plots' below for details on how model performance is affected by changes in hidden dimensionality and input dimensionality.
Appendix B An analytic solution to identity with a feed-forward network We now show that our feed-forward networks with one hidden layer can solve the samedifferent problem we pose, in the following sense: for any set of inputs, we can find parameters θ that perfectly classify those inputs. At the same time, we also show that there are always additional inputs for which θ makes incorrect predictions.
Here are the parameters of a feed forward neural network that performs a binary classification task where, if n is the dimension of entity embeddings used, then Given an input (x 1 , x 2 ), if the output o 1 is larger than o 2 , then one class is predicted; if the output o 2 is larger that o 1 , then the other class is predicted. When the two outputs are equal, the network has predicted that both classes are equally likely and we can arbitrarily decide which class is predicted. In this case, the output o 1 predicts the two inputs, x 1 and x 2 , are in the identity relation and the output o 2 predicts the two inputs are not. Now we specify parameters to provide an analytic solution to the identity relation using this network: where I is the identity matrix, −I is the negative identity matrix, and 1 and 0 are the two vectors in R n that have all zeros and all ones, respectively. The output values, given an input, are where two parameters are left unspecified, b 1 , b 2 . We present a visualization in Figure B1 of how the analytic solution to identity of this network changes depending on the values of two bias terms. In this example, the network receives two one-dimensional inputs, x 1 and x 2 . If the ordered pair of inputs is in the shaded area on the graph, then they are predicted to be in the identity relation. If in the unshaded area, they are predicted not to be. The dotted line is where the network predicts the two classes to be equally likely.
x 1 Figure B1 . A visual representation of how the analytic solution to identity of a single layer feed forward network changes depending on the values of two bias terms, b 1 , b 2 .
The network predicts x 1 and x 2 to be in the identity relation if n i=1 |x i − y i | < b 1 − b 2 which is visualized as the points between two parallel lines above and below the solution line x 1 = x 2 . As the difference b 1 − b 2 gets smaller and smaller, the two lines that bound the network's predictions get closer and closer to the solution line. However, as long as b 1 − b 2 is positive, there will always be inputs of the form (r, r + (b 1 − b 2 )/2) that are false positives. For any set of inputs, we can find bias values that result in the network correctly classifying those inputs, but for any bias values, we can find an input that is incorrectly classified by those values. In other words, we have an arbitrarily good solution that is never perfect. We provide a proof below that there is no perfect solution and so this is the best outcome possible. However, if we were to decide that, if the network predicts that an input is equally likely in either class, then this input is predicted to be in the identity relation, we could have a perfect solution with b 1 = b 2 .
Here is proof that a perfect solution is not possible. A basic fact from topology is that the set {x : f (x) < g(x)} is an open set if f and g are continuous functions. Let N o 1 and N o 2 be the functions that map an input (x 1 , x 2 ) to the output values of the neural network, o 1 and o 2 , respectively. These functions are continuous. Consequently, the set C = {(x 1 , x 2 ) : N o 2 (x 1 , x 2 ) < N o 1 (x 1 , x 2 )}, which is the set of inputs that are predicted to be in the equality relation, is open.
With this fact, we can show that, if the neural network correctly classifies any point on the solution line x 1 = x 2 , then it must incorrectly classify some point not on the solution line. Suppose that C contains some point (x, x). Then, by the definition of an open set, C contains some ball around (x, x), and therefore C contains (x, x + ), which is not on the solution line x 1 = x 2 . Thus, C can never be equal to the set {(x 1 , x 2 ) : x 1 = x 2 }. So, because C is the set of inputs classified as being in the equality relation by the neural network, a perfect solution cannot be achieved. Thus, we can conclude our arbitrarily good solution is the best we can do.

Appendix C An analytic solution to ABA sequences
Here are the parameters of a long short term memory recurrent neural network (LSTM): where, if n is the representation size and d is the network hidden dimension, then and σ is the sigmoid function. The initial hidden state h 0 and initial cell state c 0 are both set to be the zero vector. We say that an LSTM model with specified parameters has learned to produce ABA sequences if the following holds: when the network is seeded with some entity vector representation as its first input, x 1 , then the output y 1 is not equal to x 1 and at the next time step the output y 2 is equal to x 1 .
We let d = 2n + 1 and assign the following parameters, which provide an analytic solution to producing ABA sequences: Where 0 j×k is the j × k zero matrix, m k is a k dimensional vector with each element having the value m, I n×n is the n × n identity matrix, and N is some very large number. Now we show that these parameters achieve an increasingly good solution as N increases. When a value involves the number N , we will simplify the computation by saying what that value is equal to as N approaches infinity. We begin with an arbitrary input x 1 and the input and hidden state intialized to zero vectors: Then we compute the cell and hidden states at the first timestep. The cell state encodes the information of the input vector, so it can be used to recover the vector at a later time step and receives no information from the previous cell state despite the forget gate being open, because the previous cell state is a zero vector. The hidden state is the cell state scaled by one half.
Then we compute the cell and hidden states for the second timestep. Because the forget gate is completely open and the input gate is completely closed, the cell state remains the same. Because the output gate is completely open, the hidden state is the same as the cell state.
With the hidden states for the first and second time steps, we can compute the output values and find that the output at the first time step is the initial input vector scaled by one half and the output at the second time step is the initial input vector.
Appendix D Additional results plots Experiment 1 results for different hidden dimensionalities Figure D1 explores a wider range of hidden dimensionalities for our Experiment 1 model (feed-forward network with a single hidden layer; equations (4)-(5)) applied to the basic same-different task. The lines correspond to different embedding dimensionalities. Figure D2 explores a wider range of hidden dimensionalities for our Experiment 2 model (LSTM; equations (8)-(9)) applied to the sequential ABA task. The lines correspond to different embedding dimensionalities. The full training set is presented to the model in multiple epochs. Figure D3 shows the results of applying the Experiment 1 model (equations (4)-(5)) to the hierarchical same-different task. The only change from that model is that the inputs have dimensionality 4m, since the four distinct representations in task inputs are simply concatenated. The lines correspond to different embedding dimensionalities. Figure D4 shows the results of applying our Experiment 3 model (feed-forward network with two hidden layers; equations (11)-(13)) to the hierarchical same-different task. The lines correspond to different embedding dimensionalities. Figure D5 shows the results of applying our Experiment 4 model (equations (14)-(17)) to the hierarchical same-different task. In this model, the hidden dimensionality is required to be twice the input dimensionality, due to the way the components are the model are reused in a hierarchical fashion.     Mean accuracy (20 runs) 2 10 25 50 100 Figure D5 . Experiment 4 model applied to the hierarchical same-different task. Lines correspond to different input dimensionality, which determine the hidden dimensionality. These models were provided random input representations.

Experiment 4 results by input class
The hierarchical same-different task intutively has four subclasses corresponding to different inputs: • same/same: 'positive' • different/different: 'positive' • same/different: 'negative' • different/same: 'negative' Figure D6 depicts model accuracy for each of these input classes, for the 'no pretraining' model depicted in Figure 7b, which uses 25-dimensional input representations. It is noteworthy that the different/different class is the most difficult for the model. Mean accuracy (20 runs) no pretraining 3-task pretraining 5-task pretraining 10-task pretraining Mean accuracy (20 runs) no pretraining 3-task pretraining 5-task pretraining 10-task pretraining (b) Experiment 2 training set results, indicating that these models very quickly memorize the training data, creating a large gap between training performance and test performance (cf. Figure 6). Mean accuracy (20 runs) no pretraining 3-task pretraining 5-task pretraining 10-task pretraining (c) Experiment 3 training set results. These are qualitatively very much like our held-out assessment results (Figure 7a). Mean accuracy (20 runs) no pretraining 3-task pretraining 5-task pretraining 10-task pretraining (d) Experiment 4 training set results. These are very similar to our held-out assessments ( Figure 7b), with one noteworthy difference: pretraining provides small improvements in the held-out assessments, whereas 'no pretraining' clearly provides the fastest learning in the training-set evaluations Figure D7 . Training set results for the networks used in our primary assessments in the main text.