Analogical Reasoning problems pose unique challenges for both connectionist and symbolic AI systems as these entail a carefully crafted solution combining background knowledge, deductive reasoning and visual pattern recognition. While symbolic systems are designed to ingest explicit domain knowledge and perform deductive reasoning, they are sensitive to noise and require inputs be mapped to a predetermined set of symbolic features. Connectionist systems on the other hand are able to directly ingest rich input spaces such as images, text or speech and can perform robust pattern recognition even with noisy inputs. However connectionist models struggle to incorporate explicit domain knowledge and perform deductive reasoning. In this paper, we propose a framework that combines the pattern recognition capabilities of neural networks with symbolic reasoning and background knowledge for solving a class of Analogical Reasoning problems where the set of example attributes and possible relations across them are known apriori. We take inspiration from the 'neural algorithmic reasoning' approach [DeepMind 2020] and exploit problem-specific background knowledge by (i) learning a distributed representation based on a symbolic model of the current problem (ii) training neural-network transformations reflective of the relations involved in the problem and finally (iii) training a neural network encoder from images to the distributed representation in (i). These three elements enable us to perform search-based reasoning using neural networks as elementary functions manipulating distributed representations. We test our approach on visual analogy problems in RAVENs Progressive Matrices, and achieve accuracy competitive with human performance and, in certain cases, superior to initial end-to-end neural-network based approaches. While recent neural models trained at scale currently yield the overall SOTA, we submit that our novel neuro-symbolic reasoning approach is a promising direction for this problem, and is arguably more general, especially for problems where suficient domain knowledge is available.
Many symbolic reasoning algorithms can be viewed as searching for a solution in a space defined
by prior domain knowledge. Given suficient domain knowledge represented in symbolic form,
‘dificult’ reasoning problems, such as analogical reasoning, can be ‘solved’ via exhaustive search,
even though they are challenging for the average human. However, such algorithms operate on
a symbolic space, whereas humans are easily able to consume rich data such as images or speech.
Neural networks on the other end are proficient in encoding high-dimensional continuous data
and are robust to noisy inputs, but struggle with deductive reasoning and absorbing explicit
domain knowledge. ‘Neural Algorithmic Reasoning’[
Our approach essentially exploits the domain
knowledge to train a suite of neural networks, one
for each known domain predicate. For RAVENs
problems, these predicates represent rules that
might apply to ordered sets (rows) of images in a
particular problem. Further, these neural
predicates are trained to operate on a special
highdimensional representation space (‘symbolic latent
space’) that is derived, via self-supervised learning,
from the symbolic input space. Note that a purely
symbolic algorithm can consume symbolic inputs
to solve the problem exactly, however a distributed
representation can allow for real world analogical Figure 1: RPM : Problem Matrix (Top),
Anreasoning for rich input spaces such as images or swer Options (Bottom)
speech (see Fig 1 for a RAVENs problem; one can
also imagine tasks with speech inputs where the analogous example signals are high pitch
transformed versions of the original). Our approach difers from [
In general, ‘RAVEN-like’ analogical reasoning tasks can be viewed as comprising of ordered
sets 1, 2, ..., containing input samples each, an additional test set containing − 1 samples
and a target ℎ sample. Each sample where ∈ [1...], ∈ [1...] is comprised of a set
of entities and each entity ∈ has attributes from a set of predefined attributes
1, 2, ..., ∈ . Assume a predefined set of all possible rules = 1, 2..., that can hold over
sample attributes in an example set(s). For a given task the objective is to infer which rules hold
across the samples in each of the example sets in order to subsequently predict the analogous
missing sample for the test set, either by generating the target sample as in the ARC challenge
[
We adapt a variation of the neural algorithmic reasoning approach to the problem defined in Section 2, where we (i) learn a latent representation based on the symbolic representation of the tasks, via self-supervised learning; (ii) train neural networks to infer the rules involved in the problem; (iii) train a neural encoder from images to align with the symbolic latent representations in (i), and (iv) use the above elements to solve a given task via a neuro-symbolic search procedure, i.e., where the elementary predicates are neural networks. We assume the presence of a training dataset with correct answer labels for the analogical reasoning tasks. The components (i), (ii) and (iii) are trained independently as for each of them we know or can determine the inputs and the targets depending on their function. We also evaluate an alternative of (v) encoding an image to the symbolic latent space via the neural encoder in (iii) above, and decode it to symbolic form using the decoder trained in (i) on the symbolic space, on which purely symbolic search is used to solve a problem instance.
We begin with a symbolic multihot task representation , which is a series of concatenated one-hots, one for each image entity attribute. Each attribute can take a value from a finite set and hence is represented using a one-hot vector. To obtain the latent representations of the tasks, we train an auto-encoder on the symbolic task definitions S as ( S) = ( S, S) where the encoder S maps from the symbolic space to the latent space and the decoder S maps the representation from the latent space back to the symbolic space as shown in component (i) of Fig. 2. As we want to reconstruct the multihot representation, a sum of negative-log likelihood is computed for each one-hot encoding present in the multihot representation. We provide an example in C.1 where the parameters and are obtained via gradient descent on a combination of negative log-likelihood loss functions as shown in equation 1 and 2 in the appendix.
Next for every attribute, and for each applicable rule for that attribute, we train a Rule Identification neural network classifier to predict if the rule (pattern) holds for the example set. As mentioned in 2, we know the rules that can hold over attributes, giving us a definite set of networks to be trained. We refer to any rule identification network using the ( , − ) pair for which it is trained. The latent representations obtained after encoding the symbolic representations of each of the samples in the example set are concatenated and sent as input to the rule identification networks. While training a neural net for a ( , − ) pair, we categorize each example set with the specific label for that particular rule and attribute, labeling it with 0 if the rule-type is not followed, 1 if the rule-type is followed or a rule-value indicating the level of the rule-type when being followed. As each of these rule-types is deterministic, we can obtain the rule-type and value for each row using their symbolic representations. The overview can be seen in component (ii) of Fig. 2 where we see the input for these elementary neural networks and the expected output determined for the ( , − ) pair. We see in Fig. 2 that type (shape) changes in row 1 , hence the expected target for ( , ) should be 1 as type stays constant and in case of 2 as the type changes, we expect ( , ) to predict 0, indicating the rule is not obeyed. With these labels, each network is optimized using cross-entropy loss. For parameterized rules we train additional networks to predict the parameters.1 1Examples provided in appendix section C.2
As our objective to apply our approach on samples in an unstructured (image, text, speech) format, we want to develop a representation for the samples that resembles the latent representation of symbolic inputs. For this we train any neural network encoder X over the rich input space X which encodes each sample to a latent space. We want to minimize the disparity in the latent representations from the sample and its corresponding symbolic representation . For this we use S trained in 3.1. We minimize the mean squared error over all pairs of symbolic and input representations (equation shown in C.1). This enables us to use the previously learned neural networks for rule inference on our image data.
As shown in component (iv) of Fig. 2, we first use X() as inputs to find the underlying rules using the neural networks trained in section 3.2. Once we obtain the set of (rule-type, value) pairs for each attribute, we apply these neural networks for each of the answer choices by adding them to the test set. For each attribute, we obtain the output probability score for that rule-type and value. The final score is the sum of these probability scores for all the inferred rules 2. The choice with the highest score is returned as the answer.
Raven’s Progressive Matrices (RPM): is a widely accepted visual reasoning puzzle used to
test human intelligence [
As each image in a RAVENs problem can be represented symbolically in terms of the entities (shapes) involved and their attributes: Type, Size, and Color; and multiple entities in the same image have Number and Position attributes. Such attributes are also rule-governing in that rules based on these can be applied to each row and the combination of rules from all rows is used to solve a given problem. Example: for each entity, the multihot representation is of size | | + || + || where , and are the set of shapes, possible sizes and possible colors respectively. The multi-hot vector is made up of 3 concatenated one-hot vectors, one each for type, size, and color. In case of multiple components, e.g: Left-Right, we concatenate the multihots of both the entities. For our auto-encoder architecture, we train simple MLPs with a single hidden layer for both and (using loss function 1,2) in appendix. The dimensions of the layers and latent representations are chosen based on the RPM configuration.
Following [
So for every attribute and its rule-type, we train an elementary neural network classifier ( ,−) , to verify if the rule is satisfied in a given row, or pair of rows. The rules of Progression and Arithmetic are further associated with a value (e.g., Progression could have increments or decrements of 1 or 2). For rule-type Constant and ‘Distribute-three’ we train a binary classifier, and for rule-type Arithmetic and Progression, we train a multi-class classifier to also predict the value associated with the rule. An example is described in the appendix along with further details on the neural networks used.
We train a CNN-based image encoder X over the image space X which encodes each image of the problem to a latent space and minimize the disparity with the corresponding symbolic latent space as described in Section 3.3. Finally, as shown in component (iv) of Fig. 2, we find the underlying rules using the neural networks trained in section 3.2. Once we obtain the set of (rule-type, value) pairs for each attribute, we apply these neural networks for each of the 8 options by placing them in the last row. We obtain the output probability score for that attribute, rule-type and value and sum the probability scores for all the inferred rules 4 and the image with the highest score is returned as the answer.
We use the test set provided by RAVEN to evaluate rule classification networks and the final accuracy. Table 2 lists the F1 of each ( ,−) classification network across all configurations. We observe that 85% of the neural networks have an F1-score ≥ 0.90. This is corroborated by the idea that these networks are trained on latent representations of symbolic data to perform elementary functions and do well on specialized reasoning components.
Table 1 shows end-to-end accuracy for diferent RAVENs problem configurations. Our proposed neural reasoning approach (A) is where we have image input encoded by () and neural reasoning in the latent space, i.e. steps (i)-(iv) in Section 3. We also show results for 4We explain the complete pseudo-algorithm along with the scoring function in the appendix. an alternative (B), (v) mentioned in Section 3, i.e., image inputs decoded to symbolic space via ( ()) followed by purely symbolic reasoning (algorithmic solving). Results using neural reasoning in the latent space but using the correct symbolic inputs mapped via () are also shown as (c) to highlight the loss in accuracy incurred while encoding images using () .
We use ResNet+DRT from RAVEN as our baseline, human performance (provided in [
Neural reasoning from symbolic inputs, i.e. (c), accuracy consistently exceeds approach A, which can be attributed to the closer relation of the latent space to the algorithmic symbolic space. We also observe lower performance for the configurations 2x2 Grid, 3x3 Grid, and Out-In grid. Upon analysis, we find that the performance of for these configurations is relatively lower as each of these components have multiple entities and the task to transform the image into the latent space and identifying rules becomes dificult.
While more recent purely neural-network based approaches remain SOTA, we note that for the simpler configurations our neuro-symbolic approaches are competitive. We speculate that because of the complex nature and dificulty of these configurations, using more powerful neural architectures (such as transformers) for self-supervised learning of the symbolic latent space as well as for learning predicates can be useful. More generally our results provide evidence that a neuro-symbolic search using neural-network based elementary predicates, trained on a symbolic latent space, may be a promising approach for learning complex reasoning tasks, especially where domain knowledge is available.
While the results presented in this paper pertain to visual analogical reasoning problems, it
should be noted that the procedure presented in Section 3 is agnostic to the input modality.
Figure 4 illustrates analogical reasoning problems in speech and text respectively; the first task
involves analogical reasoning in speech, where the input corresponds to a speech sample in a
male voice and the output samples correspond to the same utterance in a female voice: The task
is to infer that this is the transformation involved and analogously generate the output speech
signal for the target query. Possible attributes for rules on a speech signal can include discrete
values of pitch, tone, volume or others. In the second, text-based example, inputs correspond to
positive reflections of an input passage, and the outputs correspond to negative reflections of
the same passage. Attributes for text rule identification can similarly include textual aspects
like language, sentiment and style. Note that both these examples require generation of the
missing target output which is a harder task than classification from a set of possible choices.
However, given the recent progress in conditional generation for images [
The ‘neural algorithmic reasoning’[
In this work, we have proposed a novel neuro-symbolic reasoning approach where we learn neural-network based predicates operating on a ‘symbolically-derived latent space’ and use these in a symbolic search procedure to solve complex visual reasoning tasks, such as RAVENs Progressive Matrices. Our experimental results (though preliminary, in that our predicates are composition of simple MLPs) indicate that our the approach points to a promising direction for neuro-symbolic reasoning research.
This work is supported by “The DataLab” agreement between BITS Pilani, K.K. Birla Goa Campus and TCS Research, India.
To give an overview of how the RAVEN dataset was generated, the authors used an A-SIG (Attributed Stochastic Grammar) to generate the structural representation of RPM. Each RPM is a parse tree that instantiates from this A-SIG. After this, rules and the initial attributes for that structure are sampled. The rules are applied to produce a valid row. This process is repeated 3 times to generate a valid problem matrix. The answer options are generated by breaking some set of rules. This structured representation is then used to generate images.
The RAVEN dataset provides a structural representation that is semantically linked with the image representation. The structural representation of the image space available in RAVEN makes it generalizable. As each image in a configuration follows a fixed structure, we use this knowledge to generate the corresponding symbolic representations. RAVEN has 10,000 problems for each configuration split into 6000: Train, 2000:Val and 2000:Test. We use the same split for training and validation and provide the results on the test set.
Number: The number of entities in a given layout. It could take integer values from [1; 9]. Position: Possible slots for each object in the layout. Each Entity could occupy one slot. Type: Entity types could be triangle, square, pentagon, hexagon, and circle. Size: 6 scaling factors uniformly distributed in [0:4; 0:9].
Color: 10 grey-scale colors
4 diferent rules can be applied over rule-governing attributes.
Constant: Attributes governed by this rule would not change in the row. If it is applied on Number or Position, attribute values would not change across the three panels. If it is applied on Entity level attributes, then we leave “as is” the attribute in each object across the three panels.
Progression: Attribute values monotonically increase or decrease in a row. The increment or decrement could be either 1 or 2, resulting in 4 instances in this rule.
Arithmetic: There are 2 instantiations in this rule, resulting in either a rule of summation or one of subtraction. Arithmetic derives the value of the attribute in the third panel from the first 2 panels. For Position, this rule is implemented as set arithmetics.
Distribute Three: This rule first samples 3 values of an attribute in a problem instance and permutes the values in diferent rows.
The symbolic encoder S() is trained using the following losses as described in Section 3. As we want to reconstruct the multihot representation, a sum of negative-log likelihood is computed for each one-hot encoding present in the multihot representation. Here denotes the output nodes from the decoder corresponding to the ℎ attribute and denotes the one-hot input for the same attribute. In equations 1 and 2 we use the example from RAVEN where the attributes are type, size, color, etc.
LS(, ) = ∑
−( ∈{,,,… } (
Σ )
) , = , Σ∈ LS(, ̂), where =̂ S( S()) (1) (2)
For every attribute, for each of its rule-type, we train an elementary neural network classifier to verify if the rule is satisfied in the row- this acts as our Rule Identification network. In this work, we refer to any rule identification network using a ( , − ) it is trained. For rule-type Constant and Distribute Three we train a binary classifier. The rules of Progression and Arithmetic are also associated with a value (e.g., Progression could have increments or decrements of 1 or 2), hence for rule-type Arithmetic and Progression, we train a multi-class classifier to also predict the value associated with the rule. Example: A neural pair for which is a binary classifier trained to identify if the row from the network for Center: ( ,) for Left: (,) configuration Center has constant type (shape) across the 3 panels. Similarly a neural network is a five-class classifier trained to classify if there is a progression in size in the Left component. This predicts 0 if there is no progression and predicts the progression value: increment or decrement (-2, -1, 1, 2) otherwise.
The latent representations S() obtained after encoding the symbolic representations of each of the three panels in the row are concatenated and sent as input to the neural networks. While training a neural net for a ( , − ) pair, we categorize each row with the specific label for that particular rule and attribute, labeling it with 0 if the rule-type is not followed and with 1 or rule-value indicating the level of the rule-type when being followed. As each of these rule-types is deterministic, we can obtain the rule-type and value for each row using their symbolic representations. The overview can be seen in component (ii) of Fig. 2 where we see the input for these elementary neural networks and the expected output determined for the ( , − )
pair. With these labels, each network is optimized using cross-entropy loss. Each network is a shallow MLP classifier with 1 or 2 hidden layers whose dimensions are chosen depending on the configuration and validation set. These classifiers are trained using symbolic representations for each component across the various configurations and we provide the results in Table. 2.
To learn the latent representation of the unstructured data such that it mimics the symbolic latent space, we minimize the mean squared error over all pairs of symbolic and input representations obtained from S()) and X( ) respectively. This enables us to use the previously learned neural networks for rule inference on our image data.
= Σ( ,) ( X( ) − S()) 2 (3) f f n i e s i i n i b e r a n i e d o , … , ←
0 i n { 1 , 2 , … , 8 } d 3 ← 3 ← = ← ( 3 1 , 3 2 , ) ( , ) ( + ) 3 3, e n d f o , o f e l o i h
S a c
O e v o o i , 1 3 , 2 2 , 2 3 ) i n r u l e t y p e s d ← 2 ( | > 2 ) t h e i
C n t n
D s r b t
T r e h
U e h t a n d e r l e ific ( r, ili i
P o r s i n | A i h e i t e 1 ) ! = 0 ∧ i d , … , n n ili y f