summaries: This paper targets the problem of abstract reasoning, with a special focus on the task of learning visual analogies. The authors propose a multi-stage neural network (Neural Structure Mapping, NSM) for decomposing the problem into vision relationship recognition and concept inference. They tested their model on an existing RPM (Raven's Progressive Matrices) based visual analogy benchmark that contains different systematic generalization tests and outperformed existing models. The authors made further discussion on these experimental results to support their proposals on model designs. A model called Neural Structure Mapping (NSM) is introduced to solve the task of abstract visual analogy making. The NSM model consists of a visual relationship encoder and an analogy inference engine. The visual relationship encoder extracts the visual domain elements, including object, attribute, and relation, while the analogy inference engine is a neural modular architecture that constructs the model layout based on the relation and predicts the final answer. On the dataset proposed by Hill et. al., the NSM shows better performance than other baselines. This paper tackles the problem of analogical reasoning. In particular, it presents a framework for learning the Raven Progressive Matrices (RPM) task, an abstract analogy task.  In the RPM task, a sequence of three images from a source domain are given. There is some relationship that holds for the sequence, e.g. the third image is the union of the first two. Then, given an incomplete sequence of two images from the target domain, the third image must be chosen from a list of four possible candidates.  The proposed Neural Structure Mapping (NPM) system consists of two pieces. The first piece is the Visual Relationship Encoder. Given the source sequence of images, the encoder predicts the type of relationship exhibited in the sequence. This information is passed to the second piece, the Analogy Inference Engine. The architecture of the engine is assembled dynamically, according to the predicted relationship. The assembled network takes the target sequence and the candidate matrices as input and selects the completion of the sequence from among the candidates.  The encoder is trained with the ground truth relationship labels. The engine is trained using the ground truth candidate labels.   The paper presents an experiment to test systematic generalization, in which particular attributes are held out during train time. The NSM system is found to achieve better performance.  In contrast to Hill 2019, which presents the model with semantically-contrasting alternative candidates at train time, NSM achieves good performance even when the alternative candidates are not necessarily semantically related.   This paper proposes a new architecture for learning visual analogies, based on Gentner’s Structure Mapping Theory for how humans might draw analogies. Gentner’s theory proposes representing the relationships between objects explicitly, so that this relational structure can be reused in new domains (and suggests that this commonality in structure is what permits analogies to be made between perceptually dissimilar objects). The authors propose a neural network model architecture and test it on the Raven’s Progressive Matrices dataset. The proposed architecture first splits a series of ‘source’ visual scenes into objects, attributes and the relationships between those scenes, before feeding just the relationship head into a second network. The second network then switches between two different architectures (depending on the relation fed in). The architecture in the second network (whichever is chosen) receives the ‘source’ relationship and two ‘target’ scenes before trying to predict which of a set of 4 candidate  ‘target’ scenes completes the visual analogy between source and target. The authors test their architecture on the generalisation splits in the RPM dataset and compare test accuracy results to the baseline models used by Hill et al, 2019. The authors show that their model (which builds in additional architectural structure) performs better at a subset of tests than more general architectures.
abstractText: Building conceptual abstractions from sensory information and then reasoning about them is central to human intelligence. Abstract reasoning both relies on, and is facilitated by, our ability to make analogies about concepts from known domains to novel domains. Structure Mapping Theory of human analogical reasoning posits that analogical mappings rely on (higher-order) relations and not on the sensory content of the domain. This enables humans to reason systematically about novel domains, a problem with which machine learning (ML) models tend to struggle. We introduce a two-stage neural framework, which we call Neural Structure Mapping (NSM), to learn visual analogies from Raven’s Progressive Matrices, an abstract visual reasoning test of fluid intelligence. Our framework uses (1) a multi-task visual relationship encoder to extract constituent concepts from raw visual input in the source domain, and (2) a neural module net-based analogy inference engine to reason compositionally about the inferred relation in the target domain. Our NSM approach (a) isolates the relational structure from the source domain with high accuracy, and (b) successfully utilizes this structure for analogical reasoning in the target domain.
references.authors: Aishwarya Agrawal Aniruddha Kembhavi Dhruv Batra Devi Parikh
references.title: C-vqa: A compositional split of the visual question answering (vqa) v1. 0 dataset
references.venue: arXiv preprint arXiv:1704.08243,
references.authors: Jacob Andreas Marcus Rohrbach Trevor Darrell Dan Klein
references.title: Neural module networks
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Dzmitry Bahdanau Shikhar Murty Michael Noukhovitch Thien Huu Nguyen Harm de Vries Aaron Courville
references.title: Systematic generalization: What is required and can it be learned
references.venue: In International Conference on Learning Representations,
references.authors: David Barrett Felix Hill Adam Santoro Ari Morcos Timothy Lillicrap
references.title: Measuring abstract reasoning in neural networks
references.venue: In International Conference on Machine Learning,
references.authors: David J Chalmers Robert M French Douglas R Hofstadter
references.title: High-level perception, representation, and analogy: A critique of artificial intelligence methodology
references.venue: Journal of Experimental & Theoretical Artificial Intelligence,
references.authors: Kezhen Chen Irina Rabkina Matthew D McLure Kenneth D Forbus
references.title: Human-like sketch object recognition via analogical learning
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Róbert Csordás Sjoerd van Steenkiste Jürgen Schmidhuber
references.title: Are neural nets modular? inspecting functional modularity through differentiable weight masks
references.venue: In International Conference on Learning Representations,
references.authors: Brian Falkenhainer Kenneth D Forbus Dedre Gentner
references.title: The structure-mapping engine, volume 1275
references.venue: Department of Computer Science, University of Illinois at Urbana-Champaign,
references.authors: Jerry A Fodor
references.title: The language of thought, volume 5
references.venue: Harvard university press,
references.authors: Jerry A Fodor Zenon W
references.title: Pylyshyn. Connectionism and cognitive architecture: A critical analysis
references.authors: Robert Geirhos Patricia Rubisch Claudio Michaelis Matthias Bethge Felix A Wichmann Wieland Brendel
references.title: Imagenet-trained cnns are biased towards texture; increasing shape bias improves accuracy and robustness
references.venue: arXiv preprint arXiv:1811.12231,
references.authors: Robert Geirhos Jörn-Henrik Jacobsen Claudio Michaelis Richard Zemel Wieland Brendel Matthias Bethge Felix A Wichmann
references.title: Shortcut learning in deep neural networks
references.venue: Nature Machine Intelligence,
references.authors: Dedre Gentner
references.title: Structure-mapping: A theoretical framework for analogy
references.venue: Cognitive science,
references.authors: Klaus Greff Sjoerd van Steenkiste Jürgen Schmidhuber
references.title: On the binding problem in artificial neural networks
references.venue: arXiv preprint arXiv:2012.05208,
references.authors: Felix Hill Adam Santoro David Barrett Ari Morcos Timothy Lillicrap
references.title: Learning to make analogies by contrasting abstract relational structure
references.venue: In International Conference on Learning Representations,
references.authors: Douglas R Hofstadter Melanie Mitchell
references.title: The copycat project: A model of mental fluidity and analogy-making
references.authors: N Ichien Q Liu S Fu KJ Holyoak AL Yuille H Lu
references.title: Visual analogy: Deep learning versus compositional models
references.venue: In Proceedings of the 43rd Annual Meeting of the Cognitive Science Society,
references.authors: Justin Johnson Ranjay Krishna Michael Stark Li-Jia Li David Shamma Michael Bernstein Li Fei-Fei
references.title: Image retrieval using scene graphs
references.venue: In Proceedings of the IEEE conference on computer vision and pattern recognition,
references.authors: Justin Johnson Bharath Hariharan Laurens van der Maaten Li Fei-Fei C Lawrence Zitnick Ross Girshick
references.title: Clevr: A diagnostic dataset for compositional language and elementary visual reasoning
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Justin Johnson Bharath Hariharan Laurens Van Der Maaten Judy Hoffman Li Fei-Fei C Lawrence Zitnick Ross Girshick
references.title: Inferring and executing programs for visual reasoning
references.venue: In Proceedings of the IEEE International Conference on Computer Vision, pp. 2989–2998,
references.authors: Diederik P Kingma Jimmy Ba
references.title: Adam: A method for stochastic optimization
references.venue: In 3rd Int. Conf. on Learning Representations (ICLR),
references.authors: Alex Krizhevsky Ilya Sutskever Geoffrey E Hinton
references.title: Imagenet classification with deep convolutional neural networks
references.venue: Advances in neural information processing systems,
references.authors: Brenden Lake Marco Baroni
references.title: Generalization without systematicity: On the compositional skills of sequence-to-sequence recurrent networks
references.venue: In International Conference on Machine Learning,
references.authors: Brenden M Lake Ruslan Salakhutdinov Joshua B Tenenbaum
references.title: Human-level concept learning through probabilistic program induction
references.authors: João Loula Marco Baroni Brenden Lake
references.title: Rearranging the familiar: Testing compositional generalization in recurrent networks
references.venue: In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP,
references.authors: Andrew Lovett Kenneth Forbus
references.title: Modeling visual problem solving as analogical reasoning
references.venue: Psychological review,
references.authors: Gary F Marcus
references.title: The algebraic mind: Integrating connectionism and cognitive science
references.venue: MIT press,
references.authors: Melanie Mitchell
references.title: Analogy-making as perception: A computer model
references.authors: Melanie Mitchell
references.title: Abstraction and analogy-making in artificial intelligence
references.venue: arXiv preprint arXiv:2102.10717,
references.authors: Andrew Joohun Nam James L McClelland
references.title: What underlies rapid learning and systematic generalization in humans
references.venue: arXiv preprint arXiv:2107.06994,
references.authors: Niv Pekar Yaniv Benny Lior Wolf
references.title: Generating correct answers for progressive matrices intelligence tests
references.venue: Advances in Neural Information Processing Systems,
references.authors: John Raven
references.title: The raven’s progressive matrices: change and stability over culture and time
references.venue: Cognitive psychology,
references.authors: Shaoqing Ren Kaiming He Ross Girshick Jian Sun
references.title: Faster r-cnn: Towards real-time object detection with region proposal networks
references.venue: In Advances in Neural Information Processing Systems (NIPS),
references.authors: Adam Santoro David Raposo David G Barrett Mateusz Malinowski Razvan Pascanu Peter Battaglia Timothy Lillicrap
references.title: A simple neural network module for relational reasoning
references.venue: Advances in Neural Information Processing Systems,
references.authors: Steven Spratley Krista Ehinger Tim Miller
references.title: A closer look at generalisation in raven
references.venue: In Computer Vision–ECCV 2020: 16th European Conference,
references.authors: Damien Teney Peng Wang Jiewei Cao Lingqiao Liu Chunhua Shen Anton van den Hengel
references.title: V-prom: A benchmark for visual reasoning using visual progressive matrices
references.venue: In Proceedings of the AAAI Conference on Artificial Intelligence,
references.authors: Duo Wang Mateja Jamnik Pietro Lio
references.title: Abstract diagrammatic reasoning with multiplex graph networks
references.venue: arXiv preprint arXiv:2006.11197,
references.authors: Taylor Webb Zachary Dulberg Steven Frankland Alexander Petrov Randall O’Reilly Jonathan Cohen
references.title: Learning representations that support extrapolation
references.venue: In International Conference on Machine Learning,
references.authors: Keyulu Xu Jingling Li Mozhi Zhang Simon S. Du Ken ichi Kawarabayashi Stefanie Jegelka
references.title: What can neural networks reason about
references.venue: In International Conference on Learning Representations,
references.authors: Licheng Yu Zhe Lin Xiaohui Shen Jimei Yang Xin Lu Mohit Bansal Tamara L. Berg
references.title: Mattnet: Modular attention network for referring expression comprehension
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition (CVPR),
references.authors: Chi Zhang Feng Gao Baoxiong Jia Yixin Zhu Song-Chun Zhu
references.title: Raven: A dataset for relational and analogical visual reasoning
references.venue: In Proceedings of the IEEE Conference on Computer Vision and Pattern Recognition,
references.authors: Kecheng Zheng Zheng-Jun Zha Wei Wei
references.title: Abstract reasoning with distracting features
references.venue: Advances in Neural Information Processing Systems,
references.authors: Bolei Zhou Agata Lapedriza Aditya Khosla Aude Oliva Antonio Torralba
references.title: Places: A 10 million image database for scene recognition
references.venue: IEEE Transactions on Pattern Analysis and Machine Intelligence,
references.authors: Xu
references.title: 2020)’s observation that a neural network which would have not aligned with the Bellman-Ford algorithm was found to align well with a different algorithm for the same dynamic programming problem
sections.heading: 1 INTRODUCTION
sections.text: The ability to form abstractions of ‘concepts’ from information and then reason about them is central to human intelligence (Lake et al., 2015). Abstractions enable humans to quickly learn concepts from few examples, and then reason systematically about new concepts by composing previously understood concepts (Nam & McClelland, 2021). Over the last decade, artificial neural networks have demonstrated human-level performance in building useful abstractions from data when tested on well-defined and constrained tasks. In computer vision, deep learning (DL) models that learn visual abstractions from raw images show strong validation performance on curated test datasets for image recognition (Krizhevsky et al., 2012), object detection (Ren et al., 2015), and scene classification (Zhou et al., 2017). However, unlike humans, DL models struggle with isolating these abstractions and systematically applying them to out of distribution test scenarios (Greff et al., 2020).
  One important way in which humans both build and reason about abstractions is through analogies (Mitchell, 2021). There are several theories in human cognitive science about how humans perform analogical reasoning. Structure Mapping Theory (SMT) posits that perceptual information can be broken down into a domain consisting of objects and attributes, and structural relations between the attributes in the domain (Gentner, 1983). Consequently, SMT defines an analogy as a mapping between the structural relations across two domains, with no mapping of the attributes. For example, to draw an analogy between the solar system and an atom, we can map the relational struc-
  ture (Planet revolves around Sunùñ Electron revolves around Nucleus, Sunmore massive than Planets ùñ Nucleus more massive than Electrons). However, the domain attributes, such as the Sun being yellow or hot are not mapped to the Nucleus in drawing an analogy.
  This idea behind structure mapping was utilized by Hill et al. (2019) as a prior in training ML models for learning analogies. They first constructed a dataset on learning abstract visual analogies from Raven’s progressive matrices (RPMs) (Raven, 2000). The abstract visual analogy task is made up of two rows of five context panels, and four possible candidate panels to complete the visual analogy. The learner must understand the higher-order relation constituted by the first row of three context panels, and then choose the candidate that satisfies the same relation with the two context panels in the bottom row as shown in Figure 1. Hill et al. (2019) showed that if the candidates presented during training were curated to maximize differences in structural relations, while being perceptually similar, the models performed more accurately in learning visual analogies. Thus, the authors verifed that incorporating structural differences to maximize the importance of structure mapping in the learning procedure also works for ML models.
  However, it is not feasible to build or curate datasets to always exploit a prior in the dataset to maximize structure learning. This would involve knowing a combinatorially large number of possible relational structures beforehand and manually selecting data to maximize learning these structures, a requirement that scales poorly with an increase in possible relational structures. To address this issue, we propose a two-stage Neural Structure Mapping (NSM) framework to learn abstract visual analogies (Figure 2). Our first-stage involves a visual relationship encoder that takes as input the visual context from the source domain and predicts the component visual concepts: objects, attributes and relationship in a multi-task manner. We then use the derived relation to dynamically build an analogy inference engine. Similar to structure mapping in humans, our engine utilizes only the relation from the source domain to pick the candidate panel that best fits the analogy. We incorporate compositional reasoning into our approach by using a neural module network (Andreas et al., 2016; Johnson et al., 2017b; Csordás et al., 2021) as our engine. Our modular neural engine dynamically adapt its structure to align (Xu et al., 2020) with the structural relationship, thus explicitly incorporating the structure mapping process in our NSM model.
  We train and evaluate our approach on five different generalization splits of the visual analogy dataset. These splits were proposed by Hill et al. (2019) to test systematic generalization (Bahdanau et al., 2018) across object and attribute values in learning visual analogies. We show that our relationship encoder achieves a high degree of accuracy in isolating the relationship from the source domain, and, as expected, there is no performance drop across generalization splits or training regimes. For our analogy inference engine, we empirically show that it explicitly captures the structure mapping process, while generalizing systematically in learning the structural relation across visual domains.
sections.heading: 2 RELATED WORK
sections.text: Learning Analogies Gentner (1983)’s SMT defines an analogy as a comparison in which relational predicates, but few or no object attributes, can be mapped from base to target domains. Symbolic models based on SMT (Falkenhainer et al., 1986), including those designed for RPMs (Lovett & Forbus, 2017), rely on first extracting a rule based representation of the domains from the perceptual input. Other cognitive analogy models based on Active Symbol theory (Hofstadter & Mitchell, 1994; Mitchell, 1993) or High-Level Perception theory (Chalmers et al., 1992) do not separate the structure extraction and mapping process, nor rely on mapping the structure syntax across domains. Our approach is not directly related to these models.
  Hill et al. (2019) introduced the dataset for learning analogies from RPMs and utilized several neural network architectures to directly learn from visual data. Their key contribution was to introduce the SMT prior into the dataset during candidate selection. Webb et al. (2020) introduced Temporal Context Normalization to explicitly learn visual features that can support extrapolation, and tested it on the Visual Analogy Extrapolation Challenge (VAEC) dataset. Both of these approaches are complementary to ours. Other DL approaches most similar to ours are the Part-Composition Model (Ichien et al., 2021) and Chen et al. (2019)’s approach. However, unlike our model, these models rely on availability of very structured intermediate representations like semantic segmentation maps, and do not use the extracted structural representations to explicitly configure the reasoning model.
  Abstract Reasoning Hill et al. (2019)’s dataset is directly derived from the Procedurally Generated Matrices (PGM) dataset introduced by Barrett et al. (2018) to test the ability of neural networks to perform abstract reasoning on RPM problems. RPM tests are an important measure of fluid intelligence in humans (Raven, 2000), and the PGM dataset provided a sufficiently large sample size for training neural networks on this problem. Following this work, two new RPM datasets were also released: RAVEN (Zhang et al., 2019), which utilized additional rules and structured rule annotations, and V-PROM (Teney et al., 2020), which utilized real images.
  DL approaches to RPM tasks can be roughly categorized into three types. The first is relation learning approaches, such as WReN (Barrett et al., 2018), which models all pairwise relationships between the matrix panels using relation networks (Santoro et al., 2017), and MXGNet (Wang et al., 2020), which learns row-based node embeddings and then performs a graph classification on the resulting candidate graphs. Second is rule learning approaches, such as DRT (Zhang et al., 2019), that learns a structured Stochastic Image Grammar of the abstract rules, and LEN (Zheng et al., 2019) that utilizes a logic embedding network along with a curriculum to learn with increasingly distracting features. Third is object-centric learning, such as Rel-AIR (Spratley et al., 2020), that obtains object embeddings generated via Attend-Infer-Repeat for each panel, and Pekar et al. (2020)’s method that utilizes both Variational AutoEncoders and an adversarial loss for candidate generation. Our model can be broadly fit into rule learning by way of the encoder, followed by relation learning via the analogy inference engine. However, our general approach towards explicitly extracting structure and mapping it is complimentary to these ideas and can be used in conjunction with several of them.
  Systematic Generalization Systematic generalization refers to the ability to generalize to novel concepts (out of distribution data) by understanding them as compositions of known concepts (Bahdanau et al., 2018). It is underpinned by three important characteristics: (1) systematicity, the ability to generalize to semantically related concepts; (2) productivity, the ability to iteratively apply compounding to generalize from constituent concepts to their recurrence; and (3) localism, the ability to iteratively apply reductionism to generalize from repeated constituent concepts to the singular. The ability to generalize systematically has been previously explored in human cognition (Fodor & Pylyshyn, 1988), natural language processing models (Lake & Baroni, 2018), and languagegrounded computer vision models (Agrawal et al., 2017). It has its origins in human cognition and was formalized by Fodor (1975) under the ‘Language of Thought’ hypothesis.
  Cognitive scientists have expressed reservations about the ability of connectionist models to generalize systematicitally (Fodor & Pylyshyn, 1988; Marcus, 2019). Investigation of neural language models showed that systematic generalization still poses a challenge for DL (Lake & Baroni, 2018; Loula et al., 2018). A key reason deep neural networks lack systematicity is due to their propensity towards ‘shortcut learning’ (Geirhos et al., 2018; 2020). This suggests that DL models rely on exploiting a few number of predictive features instead of considering all possible information about
  the data while drawing conclusions. Consequently, this leads to poor generalization when the key predictive features are changed, even though the central evidence remains the same. For example, DL approaches to solving RPM problems were discovered to rely on evaluating the mode across all candidates in the RAVEN dataset and a significant drop in generalization performance was observed when the models were tested without the shortcut on the RAVEN-Fair dataset (Spratley et al., 2020). On the other hand, neural module networks (Andreas et al., 2016; Johnson et al., 2017b) generalized well systematically when their layout aligned well with specific language-grounded reasoning problems (Bahdanau et al., 2018). Hence, we utilize a modular approach in building our analogy inference engine, which in turn utilizes the relationship structure inferred by our encoder to automatically align itself to the problem. This is a form of conditional computation.
sections.heading: 3 PROBLEM SETUP
sections.text: The abstract visual analogy task (Hill et al., 2019) falls under the umbrella of Raven’s Progressive Matrices (Raven, 2000) designed to test abstract reasoning and fluid intelligence in human and artificial agents. Each question consists of five context panels P 1´5con , and four candidate panels P 1´4can . The context panels are arranged in a matrix with two rows of three columns each, with the final panel in the second row missing. The first row of panels P 1´3con express a semantically related triplet R “ to, a, ru, that is composed of two lower-order perceptual visual concepts: object o and attribute a, and one higher-order semantic visual concept: relationship r. The objective is to choose a candidate c P
  Ť4 i“1tP icanu that, upon substitution in place of the missing
  panel, represents the same relationship as the first row of panels.
  The object (o P {line, shape}) and attribute (a P {quantity,colour,type,size,position}) together constitute the visual domain d of the triplet R. Each possible attribute can take ten values vpaq P t1, 2, ..., 9, 10u (normalized). The domain of the first row of panels P 1´3con defines the source domain dsource of the analogy, and the domain of the second row of panels tP 4´5con , cu defines the target domain dtarget. The dataset consists of seven unique possible domains such that d P {shape quantity, shape colour, shape type, shape size, shape position, line type, line colour}. To test the systematic generalization in learning visual analogies, the dataset has five different generalization splits that require the ability to recognize the relationship across both novel domain d and attribute a values:
  • Novel Domain Transfer: The training set consists of 42 ordered pairs of dsource and dtarget while the remaining 7 (7*7 - 42) pairs are present only in the test set i.e. dtrainsource Ś dtraintarget X dtestsource Ś
  dtesttarget “ H. • Novel Domain Type (line type and shape color) : The training set does not contain any
  problems with the held-out domain i.e. dtrain R {line type} or dtrain R {shape colour}, while each problem in the test set involves the held-out domain.
  • Novel Domain Values (Interpolation and Extrapolation): The training and test sets are made of two mutually exclusive sets of attribute values. For the extrapolation split, vpaqtrain P t1, 2, 3, 4, 5u while vpaqtest P t6, 7, 8, 9, 10u. For interpolation, vpaqtrain P t2, 4, 6, 8, 10u while vpaqtest P t1, 3, 5, 7, 9u.
  Each of the splits presents a unique challenge in terms of generalization, yet shares the idea that understanding an analogy involves identifying the higher-order visual relation from the source domain and applying it to a target domain. The relationship (r P {progression, AND, OR, XOR}) in the visual analogy dataset can be of classified into two types: Unary and Binary. The Unary relation, progression, is composed of a function applied to a single panel to produce the next panel in a row. On the other hand, the Binary relations, (AND, OR, XOR), are composed of a function applied to the first two panels in a row to generate the final panel. Thus, the relationship defines the semantics across a row of panels and is the core abstraction of analogical reasoning.
  Hill et al. (2019) hypothesized that introducing a prior on the learning process that requires the learner to correctly identify the relationship would align with how humans learn structure for analogical mapping. They designed this prior by carefully controlling the candidate panels P 1´4can presented during model training (Figure 3). This regime, called Learning Analogies By Contrasting
  (LABC), consists of candidates that are all semantically possible to complete the visual analogy. Each candidate satisfies one of the four possible relationships with the target domain panels. However, only the correct panel satisfies the relationship in the source domain panels. The authors found that LABC training significantly improved the ability to learn analogies in DL models compared to training with merely perceptually possible candidates (Normal training). In fact, even a mixed training regime consisting of both LABC and Normal problems showed significant improvement on the Normal training regime. To simplify presentation, in what follows we will use the term “Contrasting” for the use of such examples during training (LABC) and in evaluation.
sections.heading: 4 METHOD
sections.text: In our work, we take a complimentary approach to Hill et al. (2019) for learning abstract visual analogies in RPMs. Instead of depending on explicitly labeled candidates for mapping relational structure, we build a model that dynamically configures its structure based on the relational structure extracted from the source domain. Internally, our approach is made up of two different neural networks that correspond to the two separate tasks in our pipeline. The first step is the Visual Relationship Encoder, Rpred “ φpP 1´3con q, that predicts the visual relationship triplet R “ to, a, ru encoded in the source domain panels P 1´3con . Next is the Analogy Inference Engine, c “ πpP 4´5con , P 1´4can , rq, that takes the predicted source relation r, and selects the candidate c P
  Ť4 i“1tP icanu that maximizes the probability of this relation in the target domain P 4´5con . We next provide detailed discussion on each of these networks in our pipeline. For implementation details of the networks please refer to Appendix C.
sections.heading: 4.1 VISUAL RELATIONSHIP ENCODER
sections.text: The Visual Relationship Encoder, Rpred “ φpP 1´3con q, segregates the abstract relationship triplet in the source domain panels into its constituent object, attribute, and relationship. This step of our NSM model corresponds to the structure extraction phase in SMT in which humans segregate the higher-order relation concepts in perceptual information from the underlying domain concepts.
  The encoder φ is made up of a multi-task neural network. We use a convolutional neural network (CNN) Cφ to first extract a visual feature vector visiφ “ CφpP iconq for each context panel. The extracted visual features are then sequentially fed into a long short term memory network (LSTM) Rφ to generate visual sequence features seqφ of the source domain. The hidden layer vector after the third sequence panel is taken as the encoded features of the source domain seqφ “ Rφpvis1´3q. The source domain feature vector seqφ is then passed to a fully connected layer lsharedφ “ FCsharedφ pseqφq that is shared between all three visual components. The shared linear fea-
  ture vector lsharedφ is then passed through three different fully connected layers l task φ “ FC taskφ plsharedφ q for each task t P {object, attribute, relation} classification. Finally, each ltaskφ is passed through a fully connected layer outtaskφ “ FCout task
  φ pltaskφ q of sizes 2, 5, and 4 for the object, attribute, and relation prediction tasks respectively. A Softmax over the outputs outtaskφ yields a probability distribution over the possible to, a, ru values that constitute the triplet R.
sections.heading: 4.2 ANALOGY INFERENCE ENGINE
sections.text: The Analogy Inference Engine, c “ πpP 4´5con , P 1´4can , rq, maps the source relationship r extracted by the Visual Relationship Encoder to the target domain P 4´5con to identify the correct candidate c that completes the visual analogy. This step of our NSM model corresponds to the structure mapping phase in SMT, in which humans apply relations extracted from the source domain to a new domain to reason about concepts in the target domain. To generalize systematically to new domains and attribute values, we utilize a modular approach (Andreas et al., 2016) to build our analogy inference engine. Similar to Johnson et al. (2017b) and Bahdanau et al. (2018), we use modules with a generic architecture. Our engine is made up of four different types of neural modules:
  • The Stem module performs a series of convolution operations with stride=2. It takes the original grayscale images of size 1ˆ 160ˆ 160 as input and returns a visual feature map of size 8ˆ 9ˆ 9 pC ˆ H ˆW q. Each of P 4´5con and P 1´4can panels is first passed through the Stem module to extract visual features before being processed by the rest of the engine.
  • The Unary module is a residual block with two 3ˆ 3 convolution layers. It receives one feature map pC ˆH ˆW q as input, and returns one feature map of pC ˆH ˆW q as output.
  • The Binary module receives two feature maps, concatenates them along the channel dimension, and uses a 1ˆ1 convolution to project them to C dimensions. It then passes the combined feature maps through a residual block, and returns one feature map of pC ˆH ˆW q as output.
  • The Classifier module also receives two feature maps, and projects them to C dimensions. It then flattens the feature maps and passes them through two fully connected layers to generate a probability distribution over the relations.
  Each candidate panel is fed parallely to the engine to generate its predictions for all four relations. In order to generate the candidate selection, we subset the probability of relationship r (rpred during inference) for all candidates, and select the candidate with the highest corresponding probability.
  The layout of the module network is chosen adaptively from two possible layouts based on the source domain relation at inference time. Each layout first processes the individual panels through the Stem module to extract visual features, followed by the Unary module. In the first layout, the Unary module outputs for the target domain panels P 4´5con are combined using a Binary module, and the outputs for the second panel P 5con and each candidate panel P 1´4 can are combined using another Binary module (Figure 4a). The outputs of both the Binary modules are then fed into the Classifier module. In the second layout, the Unary module outputs for the target domain panels P 4´5con are similarly combined using a Binary module. However, the output of this Binary module and the Unary candidate output is directly fed into the Classifier module (Figure 4b). We provide further discussion on these layouts in Appendix A.
sections.heading: 5 EXPERIMENTS AND RESULTS
sections.heading: 5.1 VISUAL RELATIONSHIP ENCODER
sections.text: Training The Visual Relationship Encoder φ is trained using the source domain context panels P 1´3con and the visual relationship labels R “ to, a, ru. The cross-entropy loss for each task is obtained using the multi-task network’s predictions and triplet labels. The total encoder loss is calculated as a weighted sum of the individual losses for object, attribute, and relation prediction:
  Lencoder “ α ˚ Lobject ` β ˚ Lattribute ` γ ˚ Lrelationship (1)
  Empirically, we found that the values of α “ 0.5, β “ 0.5, γ “ 2.0 led to higher validation accuracy. The model was trained for 100 epochs using the Adam optimizer (Kingma & Ba, 2015) with a learning rate of 1e´ 4. For each generalization split, the model was trained with contrasting, normal, as well as mixed candidates. The model with the best validation accuracy was chosen for testing (the validation set consisted of a similar set of analogy candidates as the training set).
sections.heading: 5.1.1 RESULTS
sections.text: We test the relationship prediction accuracy of our encoder across all five generalization splits, with each possible set of analogy candidates (Contrasting, Normal, Mixed). Our relationship encoder was able to isolate the component relationship from the source domain with a high degree of accuracy (min: 82.4%, max: 86.04%) across all generalization splits and all three types of candidates (Figure 5). Furthermore, since the encoder utilizes only the source domain information in determining the relation, we observe no drop between training and test accuracy across all generalization splits.
  By identifying the visual relationship in the source domain, the output of the visual relationship encoder is able to determine the layout for the subsequent analogy inference engine. Since the inference engine chooses between only two possible layouts, a baseline that always chooses the majority class layout would lead to a correct choice in 75% of problems. Hence, our encoder must
  achieve a high degree of accuracy in identifying the correct layout to beat this baseline. Our encoder is indeed able to identify the layout matching the reasoning problem with near perfect accuracy (min: 98.42%, max: 99.9%). The full results for layout prediction across all generalization splits and training regimes are in Table 15 in Appendix D.
sections.heading: 5.2 ANALOGY INFERENCE ENGINE
sections.text: Training The Analogy Inference Engine π is trained using the target domain context panels P 4´5con , the candidate panels P 1´4can , the ground truth candidate label, and the ground truth visual relationship label r. The engine was trained for 100 epochs using the Adam optimizer with a learning rate of 1e´4. Similar to the first stage, the engine was also trained with contrasting, normal, as well as mixed candidates. The model with the highest validation accuracy was chosen for testing (validation set consisted of a similar set of analogy candidates as the training set).
  Testing For testing, we rely on the relationship label rpred predicted by our encoder instead of ground truth r. While all baselines (see below) are trained with the full set of context panels P 1´5con , our Analogy Inference Engine only utilizes the target domain panels P 4´5con for context. Hence, we also provide the results of a full context model which utilizes all context panels P 1´5con . For this purpose, we leverage our encoder which is trained with the remaining context panels P 1con – P 3 con. We use it to first extract the relationship r from the source domain as discussed in Section 4.1. In addition, we also generate candidate probabilities from the encoder during inference, by considering each candidate in parallel followed by a Softmax over the probability of r across all candidates as described in Section 4.2. The candidate probabilities of the full context NSM model are calculated as a 1:1 ensemble between the probabilities from both the inference engine and the encoder.
  Baselines We compare the candidate selection accuracy of our analogy inference engine with each model utilized by Hill et al. (2019). These baselines include a CNN-LSTM model, a standard ResNet50 (with 9 input channels for 9 panels), a parallel ResNet50 (with 6 channels and each candidate fed in parallel), and a Wide Relation Network. Each baseline is trained for 100 epochs using the Adam optimizer with a learning rate of 1e´4, with contrasting, normal, and mixed candidates.
sections.heading: 5.2.1 RESULTS
sections.text: Does the modular analogy inference engine generalize systematically?
  We hypothesize that choosing a modular engine for analogy inference enables compositional reasoning about novel domain values (objects and attributes). In Table 2 we compare the generalization performance of our engine on the Novel Attribute Value: Extrapolation and Novel Domain: Line Type test splits of the analogy dataset. Our approach achieves the highest test accuracy across all three training candidate regimes in the Novel Domain setting when tested with contrasting candidates. Furthermore, our approach yields high test accuracy (highest or within ă 1%) for the Contrasting and Normal training candidate regimes in the Novel Attribute Value setting. Thus, our NSM approach is better at systematic generalization to novel visual domains than monolithic neural
  networks. For completeness, we provide the results for both our evaluation setups across all training and test regimes in Tables 16 and 17 in Appendix D.2
  Does our model’s prior enable it learn structure mapping?
  We specifically evaluate the Normal training scenario where the candidates presented to the learner are drawn randomly and lack the contrasting prior which explicitly promotes structure learning. Since our NSM model explicitly captures and maps the structure of the visual analogy, thus making up for the lack of a prior in the candidates, we anticipate that the test performance of our model trained with normal candidates would outperform other baselines. We visualize the generalization performance of this training scenario for the Novel Domain Value: Extrapolation and Novel Domain: Line Type generalization splits in Figure 6. We observe that our model outperforms other networks when averaged across both types of candidates during testing, demonstrating that our model’s prior enables it to learns structure mapping better than other models.
  How important is structure mapping in drawing the correct analogy?
  We verify the importance of explicitly mapping structure on our NSM approach by comparing our results when the relationship label inferred in the first step matches the ground truth relationship label. We present the confusion matrix in Table 2 where it can be seen that the test candidate selection accuracy for the correct structure mapping (diagonal entries) is significantly higher than incorrect structure mapping.
sections.heading: 6 CONCLUSIONS AND FUTURE WORK
sections.text: In this work, we introduce a two-stage neural framework for learning abstract visual analogies based on the Structure Mapping Theory of human analogy making. Our first stage is a multi-task Visual Relationship Encoder that corresponds to structure extraction from perceptual information in humans. Our second stage is a modular Analogy Inference Engine that corresponds to mapping higherorder relations for structure mapping in humans. Our approach is able to generalize systematically to novel target domains, compensate for the lack of a prior in candidate selection, and successfully exploit the process of extracting and mapping the relationship structure. In future work, we plan to investigate search-based (e.g. Neural Architecture Search) as well as differentiable (e.g. attentionbased) methods for generating the layouts of our Analogy Inference Engine. Furthermore, we would like explore approaches that combine our structure mapping framework into existing methods for reasoning about Raven’s Progressive Matrices beyond analogy making.
sections.heading: A HOW DO WE CHOSE THE MODULE NETWORK LAYOUTS?
sections.text: The generic architecture of our modules allows for a combinatorially large number of possible architectural layouts of our inference engine. Previous work in language-grounded reasoning tasks like VQA (Johnson et al., 2017b) or referring expression comprehension (Yu et al., 2018) uses a semantic parse tree generated from natural language to generate layouts for neural module networks. Since our inference engine πprq relies only on the relationship label from the source domain, it lacks the rich compositional structure available in language-grounded reasoning to arrange the modular network layout. However, generating the proper layout for neural module networks is fundamental to their ability to generalize systematically (Bahdanau et al., 2018).
  As discussed in Section 4.2, we dynamically chose between two layouts of our neural module network based on the relationship type. Our rationale behind choosing these layouts comes from the knowledge of the possible relationships our engine has to reason about. Each layout aligns algorithmically (Xu et al., 2020) with a reasoning algorithm for identifying the relationship across three panels. The first layout models Algorithm 1 to identify a Unary relationship like progression (not to be confused with a Unary module) between panels 1, 2 and 3. The second layout models Algorithm 2 to identify a Binary relationship (OR, AND, XOR) across panels 1 and 2 in the last panel.
  Algorithm 1 To Identify Unary Relation Require: Panels P1, P2, P3
  1: D1 Ð extractObjectsAndAttributes(P1) 2: D2 Ð extractObjectsAndAttributes(P2) 3: D3 Ð extractObjectsAndAttributes(P3) 4: R12 Ð artihmeticOperation(D1, D2) 5: R23 Ð artihmeticOperation(D2, D3) 6: ResultÐ isConsistent(R12, R23) 7: return Result
  Algorithm 2 To Identify Binary Relation Require: Panels P1, P2, P3
  1: D1 Ð extractObjectsAndAttributes(P1) 2: D2 Ð extractObjectsAndAttributes(P2) 3: D3 Ð extractObjectsAndAttributes(P3) 4: R12 Ð binaryOperation(D1, D2) 5: ResultÐ isConsistent(R12, D3) 6: return Result
  We do not explicitly train our modules to correspond to any individual functional form. Instead, we expect the module instantiations to learn the corresponding function in the reasoning step simply by learning from the classification loss. For example, in the reasoning algorithms above, a Unary module can learn extractObjectsAndAttributes(), Binary module can learn artihmeticOperation() and binaryOperation(), and Classifier module can learn isConsistent() functions. This enables the modules to share parameters across relation functions (such as two different instantiations of binaryOperation() for AND and OR), as well as across objects and attributes. This also enables us to utilize general purpose modules which could potentially be arranged in several possible combinations depending on the reasoning problem, and can be easily extended beyond the abstract visual analogy setting of only four relationships to large number of possible relationships in real-world datasets like Scene Graph (Johnson et al., 2015) and CLEVR (Johnson et al., 2017a).
sections.heading: Do algorithmically aligned engine layouts learn corresponding relations better?
sections.text: We chose two possible layouts for our modular engine based on their alignment with algorithms for identifying a Unary or Binary relation across three panels in RPM problems. We expect LayoutA (Figure 4a) to better align with Unary (progression) problems and Layout-B (Figure 4b) to better align with Binary (AND, OR, XOR) problems. In order to verify this empirically we train each layout individually with similar training hyperparameters as the full engine. We control the overall validation accuracy to select trained models which perform similarly across the full dataset. Next, we compare the test accuracy for Unary and Binary relations for the trained Layout-A and Layout-B models in Table 3.
  In practice, we found significant stochasticity in the performance between Unary and Binary relation types across both layouts. From the observed results, we cannot conclusively say that our layouts necessarily align better with one or the other relationship problem. One possible explanation for this could be that there can be alternate algorithms for evaluating the same relation, which align algorithmically with these layouts. This is similar to Xu et al. (2020)’s observation that a neural network which would have not aligned with the Bellman-Ford algorithm was found to align well with a different algorithm for the same dynamic programming problem.
  Does having an adaptive engine enable better analogy inference?
  We use an adaptive modular engine for analogy inference which chooses between two possible module net layouts at inference time. This enables our engine to compositionally reason about the underlying relation. We expect our adaptive setup to outperform a static layout since the engine can then chose to use a better fit layout according to the mapped relationship structure. To verify our hypothesis, we compare our input-adaptive engine to a fixed engine. We chose each candidate layout described in Section 4.2 as a possible inference engine. We call these fixed models Engine-A and Engine-B, and train them similar to our full model. We then compare the test accuracy performance of our full model, which we label Engine-Full, against the test accuracy fixed models.
  Empirically, we found that the adaptive engine was not able to outperform the fixed engines, contrary to our expectation. We believe there are two main reasons for this: (1) Our individual engines are not sufficiently differentiated in their performance on their respective reasoning tasks (as shown in Table 3), so there is not a significant performance gain in choosing one over the other, and (2) the number of possible reasoning scenarios is quite limited in the abstract visual analogy problem, and hence the adaptive engine is not able to benefit from learning a large number of mixture of experts.
  B VISUAL RELATIONSHIP ENCODER ABLATIONS
  B.1 MULTI-TASK VERSUS MULTI-LABEL VISUAL RELATIONSHIP ENCODER
  In our two-step structure mapping approach, we treat the structure extraction problem as a multitask learning problem where the relationship, object, attribute prediction are treated as separate learning tasks. We could have alternatively treated the structure extraction problem as a multi-label classification problem and instead predicted the full triplet R “ to, a, ru from our model. A multi-label problem could in principle learn from added network interactions between the final classification layer weights for the domain components.
  In order to draw a comparison between both these learning approaches, we trained a multi-label visual relationship encoder which predicts the triplet R “ to, a, ru as its output. We replaced the ltaskφ “ FC taskφ plsharedφ q layers in out multi-task encoder with a l shared2 φ “ FC shared2 φ plsharedφ q layer, and the final classifiers outtaskφ “ FCout task
  φ pltaskφ q of sizes 2, 5, and 4, with one classifier outφ “ FCoutφ pl shared2 φ q of size 11 (2+5+4). For training, we used exactly the same procedure as the multitask encoder (described in Section 5.1).
  We compared the performance of these models by evaluating there test accuracy across three different generalization splits: Novel Domain Transfer, Novel Domain: Line Type, and Novel Attribute Value: Extrapolation. Since our encoder is not trained with the candidate panels, we restrict ourselves to one training regime (Contrasting) for this comparison. Our observations are reported below in Table 6.
  We found the performance of the two types of relationship encoders to be quite similar in terms of the test accuracy for predicting the relationship from the source domain panels. In fact, the multilabel encoder was slightly better than the multi-task encoder across all generalization splits. Despite this, we still went ahead with using the multi-task encoder in our two-step approach since the multitask learning network scales much better with the number of objects, attributes, and relationships in the perceptual domain.
  B.2 MULTI-TASK VERSUS RELATIONSHIP-ONLY VISUAL RELATIONSHIP ENCODER
  We also performed an ablation study on predicting only the visual relationship from the encoder and comparing it with the full-task of predicting relationship, object, attribute. We found that predicting only the relationship structure is competitive with a multi-task predictor in the Novel Domain Transfer regime, and since our encoder does not perform generalization across domains or candidate types this should hold for other regimes as well. This does not take away from our central contribution of incorporating structure mapping into our model, rather it only highlights the importance of structure extraction as the first-step of our model.
  C IMPLEMENTATION DETAILS
  C.1 VISUAL RELATIONSHIP ENCODER
  Index Layer Output Size 1 Panel Image Input 1 x 160 x 160 2 Conv(3 x 3, 1Ñ 8, stride 2) 8 x 79 x 79 3 BatchNorm 8 x 79 x 79 4 ReLU 8 x 79 x 79 5 Conv(3 x 3, 8Ñ 8, stride 2) 8 x 39 x 39 6 BatchNorm 8 x 39 x 39 7 ReLU 8 x 39 x 39 8 Conv(3 x 3, 8Ñ 8, stride 2) 8 x 19 x 19 10 BatchNorm 8 x 19 x 19 12 ReLU 8 x 19 x 19 13 Conv(3 x 3, 8Ñ 8, stride 2) 8 x 9 x 9 14 BatchNorm 8 x 9 x 9 15 ReLU 8 x 9 x 9 16 FC(8*9*9Ñ 128) 128 17 BatchNorm 128 15 ReLU 128
  Table 8: Encoder LSTM architecture
  Index Layer Output Size 1 Encoder-LSTM final hidden state 128 3 FC(128Ñ 128) 128 7 ReLU 128 4 FCtask(128Ñ 64) 64 7 ReLU 64 5 FCclassifiertask (64Ñ |Task| ) |Task|
  Table 9: Encoder Multi-Task classifier architecture. |Task| = 2, 5, 4 for object, attribute, and relationship classifiers respectively
  C.2 ANALOGY INFERENCE ENGINE
  Index Layer Output Size 1 Panel Image Input 1 x 160 x 160 2 Conv(3 x 3, 1Ñ 8, stride 2) 8 x 79 x 79 3 BatchNorm 8 x 79 x 79 4 ReLU 8 x 79 x 79 5 Conv(3 x 3, 8Ñ 8, stride 2) 8 x 39 x 39 6 BatchNorm 8 x 39 x 39 7 ReLU 8 x 39 x 39 8 Conv(3 x 3, 8Ñ 8, stride 2) 8 x 19 x 19 10 BatchNorm 8 x 19 x 19 12 ReLU 8 x 19 x 19 13 Conv(3 x 3, 8Ñ 8, stride 2) 8 x 9 x 9 14 BatchNorm 8 x 9 x 9 15 ReLU 8 x 9 x 9
  Table 10: Stem module architecture
  Table 11: Unary module architecture
  Index Layer Output Size 1 Previous Module Output 8 x 9 x 9 2 Previous Module Output 8 x 9 x 9 3 Concatenate (1) and (2) 16 x 9 x 9 4 Conv(1 x 1, 16Ñ 8) 8 x 9 x 9 5 ReLU 8 x 9 x 9 6 Conv(3 x 3, 8Ñ 8) 8 x 9 x 9 7 ReLU 8 x 9 x 9 8 Conv(3 x 3, 8Ñ 8) 8 x 9 x 9 9 Residual: Add (5) and (8) 8 x 9 x 9 10 ReLU 8 x 9 x 9
  Table 12: Binary module architecture
sections.heading: D SUPPLEMENTARY RESULTS
sections.text: D.1 VISUAL RELATIONSHIP ENCODER
  D.2 ANALOGY INFERENCE ENGINE
title: NEURAL STRUCTURE MAPPING FOR LEARNING ABSTRACT VISUAL ANALOGIES