PaperlayerView exact revision on arXiv

Source-linked AI summary

A Neuro-vector-symbolic Architecture for Solving Raven's Progressive Matrices

Michael Hersche, Mustafa Zeqiri, Luca Benini, Abu Sebastian, Abbas Rahimi

arXiv:2203.04571v2cs.LGcs.AIcs.CV

TL;DR

RAVEN answer choices can permit context-blind shortcut solving, motivating evaluation on unbiased I-RAVEN. NVSA uses structured VSA representations in its perception and reasoning pipeline; it outperforms comparison methods on RAVEN, leads I-RAVEN, and is competitive on PGM.

  • Problem

    RAVEN answer choices can permit context-blind shortcut solving, so unbiased I-RAVEN is recommended for testing RPM reasoning models.

    Source: RAVEN and I-RAVEN dataset containing… · p. 9

  • Method

    NVSA uses structured VSA representations to encode objects and support perception and higher-level reasoning in a unified framework.

    Source: §IV · p. 8

  • Results

    87.7% average accuracy on RAVEN, outperforming SCL by 0.5% and PrAE by 27.4%; NVSA also achieves the highest I-RAVEN accuracy and is competitive with reproduced MRNet on PGM.

    Source: §III · p. 7

  • Takeaways & Limitations

    NVSA is a step toward a unified framework for tasks involving both perception and higher-level reasoning.

    Source: §IV · p. 8

    The frontend requires storing and searching dictionary W, though smaller codebooks and resonator networks are proposed as a potential alternative.

    Source: §IV · p. 8

Abstract

from arXiv · show

Neither deep neural networks nor symbolic AI alone has approached the kind of intelligence expressed in humans. This is mainly because neural networks are not able to decompose joint representations to obtain distinct objects (the so-called binding problem), while symbolic AI suffers from exhaustive rule searches, among other problems. These two problems are still pronounced in neuro-symbolic AI which aims to combine the best of the two paradigms. Here, we show that the two problems can be addressed with our proposed neuro-vector-symbolic architecture (NVSA) by exploiting its powerful operators on high-dimensional distributed representations that serve as a common language between neural networks and symbolic AI. The efficacy of NVSA is demonstrated by solving the Raven's progressive matrices datasets. Compared to state-of-the-art deep neural network and neuro-symbolic approaches, end-to-end training of NVSA achieves a new record of 87.7% average accuracy in RAVEN, and 88.1% in I-RAVEN datasets. Moreover, compared to the symbolic reasoning within the neuro-symbolic approaches, the probabilistic reasoning of NVSA with less expensive operations on the distributed representations is two orders of magnitude faster. Our code is available at https://github.com/IBM/neuro-vector-symbolic-architectures.

I. NVSA FRONTEND: PERCEPTION

The NVSA frontend uses fixed-width VSA vectors as a shared interface: object attributes compose into scene representations, and a neural network maps panels into that space.

I. NVSA FRONTEND: PERCEPTION

  • The frontend combines a trainable neural network with VSA algebra so that data-driven panel representations share a fixed-width language with structured object descriptions.The resulting representations are intended to support downstream reasoning without exploding dimensionality or facing superposition catastrophe.Source: §I · p. 3

A. Defining VSA representations

  • Binding attribute codewords yields quasi-orthogonal object vectors, while bundling preserves similarity to constituent objects in a scene representation.This lets multiple objects be represented in a fixed dimensionality without the superposition catastrophe described for naive representations.Source: A. Defining VSA representations · p. 3

B. Neural network representation learning over VSA

  • A ResNet-18 maps each panel to a 512-dimensional tanh-bounded query that is matched against the object dictionary W.The dictionary is generated once and remains frozen during training; the VSA representation can encode multiple objects without requiring separate segmentation and recognition networks.Source: A. Defining VSA representations · p. 3, B. Neural network representation… · p. 4
  • Multiplicative binding does not generalize to unseen combinations of attribute values, while multiplicative-additive encoding generalizes up to 72%.The multiplicative encoding does generalize to unseen combinations of multiple objects.Source: B. Neural network representation… · p. 4

C. Inferring probability mass functions from data-driven VSA representations

The frontend derives probability mass functions (PMFs) from panel images, and the backend transforms them into VSA representations for probabilistic reasoning over rules.

C. Inferring probability mass functions from data-driven VSA representations

  • Panel queries are decomposed against the object dictionary to infer attribute PMFs, which are combined into five panel-level distributions for position, number, type, size, and color.Context-panel PMFs form probabilistic scene representations that the backend transforms to find an underlying rule.Source: C. Inferring probability mass… · p. 4

II. NVSA BACKEND: REASONING

  • The backend transforms inferred PMFs into a vector space where VSA operators implement logical rules and support computing each rule’s probability.It selects the most probable rule for execution.Source: §II · pp. 4–5

A. VSA representations of probability mass functions

  • Binary sparse block codes represent PMFs so that the backend can handle both discrete and continuous attributes; fractional power encoding supplies continuous-value codewords.A PMF is represented as a weighted superposition of its codewords, with PMF values used as weights.Source: A. VSA representations of probability… · p. 5

B. VSA-based probabilistic abduction and execution

The backend evaluates rules by manipulating VSA representations of panel PMFs, then uses the selected rule to estimate the missing panel’s distribution.

B. VSA-based probabilistic abduction and execution

  • For arithmetic addition, binding continuous number-PMF representations forms row vectors whose similarities, with additional constraints, estimate rule probability.Under maximally compact PMFs, fractional power encoding makes the bound vector correspond to the sum of the first two panel values.Source: B. VSA-based probabilistic abduction… · p. 5
  • For distribute three, the backend represents 3×3-grid positions as discrete codes and checks whether row and column product vectors are similar across rows and columns.The rule requires the same position values to appear in each row with a distinct permutation, and likewise across columns.Source: B. VSA-based probabilistic abduction… · p. 6
  • After selecting a rule, the backend unbinds known attribute vectors and searches the codebook to estimate the missing-panel PMF.The estimated missing-panel representation can contain noise terms when the context PMFs are not maximally compact.Source: B. VSA-based probabilistic abduction… · p. 6
  • NVSA’s associative-memory search takes O(n) time and space, compared with up to O(n^3) for exhaustive symbolic rule search.For distribute three on a 3×3 grid, exhaustive search can involve at least 26·10^7 rule implementations; VSA operations search over the space in superposition.Source: B. VSA-based probabilistic abduction… · p. 6

C. End-to-end training

End-to-end training passes context and candidate panels through the frontend and backend, using answer scores and rule supervision to train the neural component.

C. End-to-end training

  • Training infers PMFs for context and candidate panels, obtains rule beliefs per attribute, samples rule actions, and scores candidates by summed Jensen–Shannon divergence.Only the ResNet-18 is trainable; the dictionary and backend parameters remain frozen.Source: C. End-to-end training · p. 7
  • Each training example supplies eight context panels, eight candidate answers, the correct answer, and the ground-truth rule for each attribute.The method uses both answer selection and rule labels in training.Source: C. End-to-end training · p. 7
  • The answer-panel scores provide a reward for a REINFORCE-based loss combined with an auxiliary loss on ground-truth rules.The auxiliary loss trains the frontend to map context panels to PMFs from which rule detection yields the correct rule.Source: C. End-to-end training · p. 7

III. RESULTS

NVSA outperforms comparison methods on RAVEN and I-RAVEN, and its reasoning backend substantially reduces search time while maintaining high accuracy. The discussion identifies dictionary and associative-memory demands as implementation considerations and presents NVSA as a unified framework for perception and reasoning.

III. RESULTS

  • 87.7% average accuracy on RAVEN and 88.1% on I-RAVEN place NVSA ahead of SCL and PrAE on both datasets.The reported margins are 0.5% and 27.4% on RAVEN, and 4.2% and 17.0% on I-RAVEN, respectively.Source: §III · p. 7
  • On the 3x3 grid, NVSA reasoning takes 63.2 minutes, 244× faster than unrestricted PrAE, while achieving 96.89% accuracy versus 97.50%.Unrestricted PrAE requires 15,408 minutes and more than 53 GB of memory; NVSA requires less than 10 GB.Source: §III · p. 7
  • On PGM, NVSA achieves 68.3% average accuracy and is reported as highly competitive with reproduced state-of-the-art MRNet.The paper describes NVSA as the first neuro-symbolic approach targeting PGM.Source: §III · p. 7
  • NVSA outperforms LEN and CoPINet on all evaluated unseen attribute-rule pairs in I-RAVEN.The evaluation withholds a target attribute-rule pair from training.Source: §III · pp. 7–8

IV. DISCUSSION

  • The frontend can express more object combinations than vector-space dimensions, but currently requires storing and searching dictionary W.Resonator networks and stochastic nonlinear variants are proposed as possible ways to reduce dictionary storage and decomposition costs.Source: §IV · p. 8
  • Associative-memory search is central to perception and reasoning; analog in-memory computing is proposed as a path to O(1) search timing.The discussion also notes that binding and bundling may benefit from low-power hardware implementation.Source: §IV · p. 8

III. RESULTS

  • NVSA reduces distribute-three rule-search complexity from O(n3) to O(n), corresponding to two orders of magnitude shorter execution.The backend uses binding and unbinding followed by a linear associative-memory search over atomic codebook vectors.Source: §IV · p. 8

IV. DISCUSSION

  • The authors frame NVSA as a step toward a unified framework for AI tasks that combine perception and higher-level reasoning.Its VSA representations and operators are described as enhancing both perception and reasoning.Source: §IV · p. 8

METHODS

The methods define RPM tasks, their attributes and row-wise rules, then describe how object-level and panel-level attribute distributions are represented. They also note that RAVEN answer choices permit a shortcut that I-RAVEN is designed to remove.

METHODS

  • RAVEN tasks ask a model to infer row-wise rules from an incomplete 3×3 matrix and select among eight candidate panels; its seven constellations each contain 10,000 samples.The samples are divided into six training folds, two validation folds, and two test folds.Source: RAVEN and I-RAVEN dataset containing… · p. 9
  • Panels contain objects described by number, position, type, size, and color, with each attribute governed row-wise by a constant, progression, arithmetic, or distribute-three rule.The number and position ranges depend on the constellation.Source: RAVEN and I-RAVEN dataset containing… · p. 9
  • RAVEN answer choices can be solved by taking the mode of an attribute across choices without examining the context, whereas I-RAVEN uses an attribute bisection tree to balance answer modifications.The paper identifies I-RAVEN as the unbiased alternative for evaluating RPM reasoning models.Source: RAVEN and I-RAVEN dataset containing… · p. 9
  • Object attribute PMFs are estimated by summing non-negative cosine similarities over valid attribute-value combinations, then applying a scaled softmax to obtain normalized distributions.For object existence, the no-object value is represented by similarity to a vector indicating an empty position.Source: PMF computation for object attributes… · pp. 9–10
  • The method combines object PMFs into panel-level PMFs for position, number, type, size, and color, with constellation-dependent occupancy and an inconsistency state for type, size, and color.The position PMF represents object occupancy; the number PMF is derived from it.Source: PMF computation for object attributes… · p. 10

PMF transformation of discrete and continuous attributes to VSA

NVSA represents attribute PMFs with VSA vectors, using unrelated sparse basis vectors for discrete attributes and fractional power encoding for continuous ones.

PMF transformation of discrete and continuous attributes to VSA

  • A discrete attribute PMF is represented in a vector space spanned by unrelated basis vectors.Each basis vector is a d-dimensional κ-sparse binary vector divided into κ blocks, each with one nonzero element.Source: PMF transformation of discrete and… · p. 10
  • For continuous attributes, fractional power encoding defines value vectors by exponentiating a randomly initialized unitary basis vector.The paper notes that RPM attributes use integer values, yielding a finite κ-sparse codebook.Source: PMF transformation of discrete and… · p. 10
  • A continuous-attribute PMF is transformed into a VSA representation using weighted superposition of its codebook vectors.Source: PMF transformation of discrete and… · p. 10

End-to-end training

End-to-end training updates the trainable frontend using answer and rule information, while the experimental setup specifies the datasets, model configuration, and training procedure. The supplementary investigation covers supervised frontend learning and generalization to unseen combinations.

End-to-end training

  • Training uses answer-panel scores derived from negative JSD and updates frontend parameters with categorical cross-entropy, a REINFORCE term, and an auxiliary ground-truth-rule term.The first term minimizes answer loss, the second uses the sampled-rule log probability, and the third improves rule detection.Source: End-to-end training · pp. 10–11

Experimental Setup

  • NVSA is trained on RAVEN and tested on both RAVEN and I-RAVEN using 512-dimensional bipolar frontend vectors and 1024-dimensional binary sparse backend codes with κ=4.A separate model is trained per constellation; training runs for 150 epochs, with batch size 16 for most constellations and 8 for the 3x3 grid.Source: Experimental Setup · p. 11

Supplementary Note 1: Neural network representation learning over VSA and its generalization

  • The supplementary investigation studies direct supervised frontend training with attribute labels and evaluates generalization to unseen attribute-value and multiple-object combinations.It also compares object classification accuracy against other losses and perceptual methods.Source: Supplementary Note 1: Neural network… · p. 20

a. Supervised training with additive cross-entropy loss and comparisons

The section evaluates NVSA perception training and the frontend’s generalization to unseen attribute-value combinations. The additive cross-entropy frontend performs strongly on panel perception, while generalization depends on the object encoding.

a. Supervised training with additive cross-entropy loss and comparisons

  • 99.76% versus 97.33% average panel accuracy results from additive versus randomized cross-entropy training on the full training set.Training on 6,000 rather than 42,000 samples nearly preserves accuracy: 99.76% versus 97.16% with additive loss, and 97.33% versus 96.78% with randomized loss.Source: a. Supervised training with additive… · p. 21, Table I · p. 21
  • 98.5% on RAVEN and 99.0% on I-RAVEN are the highest accuracies reported for the full RPM tests using the trained NVSA frontend and backend.The authors attribute these results to accurate perception.Source: a. Supervised training with additive… · p. 21

b. Generalizability of multiplicative binding to unseen combinations of attribute values

  • The multiplicative encoding yields 0% test accuracy across all six attribute pairs in both unseen-combination settings.The training and test combinations are mutually exclusive, and their quasi-orthogonal dictionary vectors do not support accurate predictions for unseen combinations.Source: b. Generalizability of multiplicative… · pp. 21–22
  • Multiplicative-additive encoding bundles key-bound attribute values, allowing each attribute to be unbound individually without knowing the other values.This disentanglement supports regression for color and size using hyperspherical prototypes, while position and type use categorical cross-entropy.Source: b. Generalizability of multiplicative… · p. 22
  • Multiplicative-additive encoding reaches 34.8% for position-color, 15.1% for position-size, 29.3% for color-size, and 72% for color-type generalization.Position-type and size-type remain at 0%.Source: b. Generalizability of multiplicative… · p. 22

c. Generalizability of multiplicative binding to unseen combinations of multiple objects

The section tests generalization across object counts and describes visual analogy solving with NVSA representations. Results vary with panel complexity, while source-domain relationships can be applied to target panels through binding.

c. Generalizability of multiplicative binding to unseen combinations of multiple objects

  • 97.1% average panel accuracy across all 2×2 test settings follows training with two-object panels; the OOD average is 97.3%.With one-object training alone, accuracy is 92.4% for two-object and 68.1% for three-object tests, falling to 19.3% for four-object tests.Source: c. Generalizability of multiplicative… · p. 23, Table III · p. 24
  • 86.3% average panel accuracy is achieved in the 3×3 setting after training only on panels with fewer than half the maximum number of objects.Training with up to two objects yields non-zero accuracy through eight-object tests, but not the nine-object test; OOD average accuracy increases with the number of objects included in training.Source: c. Generalizability of multiplicative… · pp. 23–24

d. Resolution issues in the RAVEN dataset

  • 42.15% of RAVEN panels are affected by visually identical inner square objects whose size labels differ by one value.The authors attribute this issue to insufficient image resolution and merge classes with identical image representations when validating perception accuracy.Source: d. Resolution issues in the RAVEN… · p. 24

Supplementary Note 2: Visual Analogies

  • Binding source-domain neural representations captures a relationship that can be applied to novel target circumstances using another binding operation.The analogy setup uses a newly generated RAVEN-like test dataset with four panels arranged in a 2×2 matrix and a missing bottom-right panel.Source: Supplementary Note 2: Visual Analogies · p. 25

a. One-to-one relationship

  • 100% accuracy is achieved on generated one-to-one analogies using the NVSA frontend and associative-memory cleanup.A solution counts as correct when the ground-truth object representation has the highest cosine similarity to the generated answer.Source: a. One-to-one relationship · p. 26

b. One to many relationship

The section applies NVSA to one-to-many visual analogies and describes VSA representations of probability mass functions. Binding can transfer multiple relationships together, while the backend uses vector operations to manipulate PMFs.

b. One to many relationship

  • Binding the source panels captures a bundle of one-to-one relationships because VSA binding distributes over bundling.Binding that relationship vector with the target panel applies the relationships simultaneously; 2,000 one-to-many problems were generated.Source: b. One to many relationship · p. 26
  • 100% accuracy is achieved on the generated one-to-many visual analogy tasks using the same frontend as for one-to-one analogies.One binding applies the source relationship set to the target representation in superposition.Source: b. One to many relationship · p. 26

VSA representation of PMFs

  • PMFs are represented as weighted superpositions of codewords, then manipulated in vector space to estimate rule probabilities and produce a missing-panel PMF.Although both FHRR and binary sparse block codes represent discrete PMFs, FHRR has difficulty representing continuous PMFs, so the backend uses sparse binary block codes.Source: VSA representation of PMFs · p. 28

Rule probability computation and rule execution

The NVSA backend estimates rule probabilities and executes selected rules using vector representations of panel attributes. Its operations vary by rule, including binding or unbinding for continuous-valued relationships and direct reuse for the constant rule.

Rule probability computation and rule execution

  • Arithmetic plus tests whether binding the first two panels matches the third; arithmetic minus is implemented analogously with unbinding.The arithmetic rule concerns continuous concepts and uses a dictionary constructed by fractional power encoding.Source: Rule probability computation and rule… · pp. 29–30
  • Rule probabilities in the NVSA backend derive from similarities between fixed-dimensional vectors, whereas PrAE computes them by marginalizing possible rule implementations.The authors relate the two approaches’ rule-probability computations in Supplementary Table IV.Source: Rule probability computation and rule… · p. 29, Table IV · p. 31
  • Progression is tested by unbinding adjacent panels and checking whether the differences match the expected increment or decrement.The zero-vector comparison distinguishes progression from the constant rule, which can be interpreted as a progression of zero.Source: Rule probability computation and rule… · p. 30
  • Distribute three is tested by comparing row and column representations, while the constant rule uses row-wise similarities.Executing the constant rule requires no vector-space transformation; the missing-panel PMF can be estimated directly from a PMF in the bottom row.Source: Rule probability computation and rule… · pp. 30–31

Selection of the rule and the final answer

NVSA infers the missing panel by executing each attribute’s highest-probability rule and selecting the candidate with the lowest summed Jensen–Shannon divergence. On unseen I-RAVEN attribute-rule pairs, it outperforms both baselines, with minor accuracy degradations on continuous rules.

Selection of the rule and the final answer

  • For each attribute, NVSA selects the highest-probability rule, executes it to estimate the missing-panel distributions, then chooses the candidate with the lowest summed JSD.The score sums the Jensen–Shannon divergences across five attribute distributions.Source: Selection of the rule and the final… · p. 31

Supplementary Note 4: Out-Of-Distribution generalization to unseen attribute-rule pairs

  • The OOD test trains without one target attribute-rule pair and tests exclusively on examples containing that pair.Training, validation, and test sets are filtered from the existing RAVEN and I-RAVEN splits.Source: Supplementary Note 4:… · p. 32
  • NVSA outperformed LEN5 and CoPINet by a large margin on every tested unseen I-RAVEN attribute-rule pair, with minor accuracy degradations on continuous rules.The authors suggest continuous rules may be important for learning all attribute values properly.Source: Supplementary Note 4:… · p. 32

PGM Dataset

The PGM dataset extends RPM problems with line and shape constellations and rules that may operate across rows or columns. NVSA adapts its frontends, scene representations, and rule processing to these structures.

PGM Dataset

  • Each PGM example has 1–4 active rules applied row-wise or column-wise, unlike RAVEN, where only a row-wise rule governs every attribute.PGM provides 1,200,000 training, 20,000 validation, and 200,000 test examples; its active-rule meta-labels omit rule orientation.Source: PGM Dataset · p. 33

NVSA frontend

  • To simplify end-to-end training, NVSA uses four ResNet-18 frontends, each handling two attributes, because a single frontend often learned only one attribute in PGM.The authors note PGM’s shape constellation has 6,300 attribute combinations versus 2,700 in RAVEN’s largest 3×3 grid constellation.Source: NVSA frontend · p. 33

Probabilistic scene representation

  • For logical rules on color, size, and type, NVSA adds extended scene PMFs that represent occupied-value combinations, limiting each set to four values to reduce compute and memory demands.The scene representations also retain standard PMFs for these attributes.Source: Probabilistic scene representation · pp. 33–34

NVSA backend

  • NVSA computes rule probabilities along rows and columns; progression and consistent union use VSA operations, while XOR, OR, and AND are evaluated in the original PMF space.Column-wise processing feeds the transposed context matrix to the backend.Source: NVSA backend · p. 34

Selection of the final answer

NVSA scores candidate answers by weighted attribute-wise JSD and learns attribute weights for PGM, where only some attributes have active rules. On PGM, its average accuracy is competitive with reproduced MRNet, though the reproduced result is below MRNet’s reported literature accuracy.

Selection of the final answer

  • Candidate scores sum attribute-wise JSD, with equal weights on RAVEN and learned weights on PGM because only 1–4 attributes have active rules.The PGM MLP predicts weights from rule probabilities, their maximizing values, and JSD errors.Source: Selection of the final answer · p. 35

Training details

  • Frontends are trained separately on rule-filtered examples, and the PGM attribute-selection MLP is trained afterward on a random subset of the full training data.The shape frontends train for 45 epochs and the line frontend for 25; the MLP uses 128 randomly selected batches per epoch.Source: Training details · pp. 35–36

Experimental results

  • 68.3% average accuracy: NVSA was competitive with reproduced MRNet on PGM, whose reported literature accuracy was 93.4% but scratch reproduction yielded 68.3%.The authors report averages over five runs for NVSA and reproduced baselines.Source: Experimental results · p. 36
Loading 2203.04571v2…