PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part II: Applications, Cognitive Models, and Challenges

Denis Kleyko, Dmitri A. Rachkovskij, Evgeny Osipov, Abbas Rahimi

arXiv:2112.15424v3cs.AI

TL;DR

HDC/VSA lacked a comprehensive account of its applications and broader cognitive uses. This Part II survey synthesizes applications, cognitive modeling, architectures, and open challenges alongside Part I’s foundations. It reports applications ranging from sequence-memory modeling and visual analogy-making to classification and DNA string matching, while identifying scaling and representation-construction challenges.

  • Problem

    No previous article comprehensively covered all known HDC/VSA applications, while existing surveys addressed particular application areas or types.

  • Method

    The paper surveys HDC/VSA applications, cognitive modeling and architectures, and future challenges, complementing Part I’s coverage of models and data transformations.

  • Results

    The survey documents applications including sequence-memory modeling, visual analogy-making, classification, and DNA string matching.

  • Takeaways & Limitations

    The survey provides newcomers and practitioners with a guide to HDC/VSA applications and identifies directions for further research and exploitation.

  • Takeaways & Limitations

    Real-world scaling of HDC/VSA-based solutions remains insufficiently demonstrated, and transforming unstructured non-symbolic data into hypervectors can be non-trivial and usually not learned.

Abstract

from arXiv · show

This is Part II of the two-part comprehensive survey devoted to a computing framework most commonly known under the names Hyperdimensional Computing and Vector Symbolic Architectures (HDC/VSA). Both names refer to a family of computational models that use high-dimensional distributed representations and rely on the algebraic properties of their key operations to incorporate the advantages of structured symbolic representations and vector distributed representations. Holographic Reduced Representations is an influential HDC/VSA model that is well-known in the machine learning domain and often used to refer to the whole family. However, for the sake of consistency, we use HDC/VSA to refer to the field. Part I of this survey covered foundational aspects of the field, such as the historical context leading to the development of HDC/VSA, key elements of any HDC/VSA model, known HDC/VSA models, and the transformation of input data of various types into high-dimensional vectors suitable for HDC/VSA. This second part surveys existing applications, the role of HDC/VSA in cognitive computing and architectures, as well as directions for future work. Most of the applications lie within the Machine Learning/Artificial Intelligence domain, however, we also cover other applications to provide a complete picture. The survey is written to be useful for both newcomers and practitioners.

1 INTRODUCTION

Part II surveys HDC/VSA applications, cognitive modeling, architectures, and challenges, addressing the field’s previously missing comprehensive overview. It complements Part I’s foundations with broad, accessible coverage of current applications and future directions.

  • HDC/VSA combines high-dimensional distributed representations with structured symbolic representation through mathematical properties of high-dimensional random spaces.
  • The survey responds to growing interest in alternative computing paradigms, including neuromorphic and nanoscalable computing, where HDC/VSA is expected to play an important role.
  • The application survey organizes major domains into deterministic behavior, similarity estimation, classification, cognitive computing, and cognitive architectures, with finer clusters listed in Table 1.
  • Before this survey, no comprehensive article covered all currently known HDC/VSA applications; existing works focused on particular areas or application types.
  • Part II covers applications, cognitive modeling, cognitive architectures, discussion, challenges, and conclusions, following Part I’s treatment of models and data-to-hypervector transformations.

2 APPLICATION AREAS

The survey groups HDC/VSA applications into deterministic behavior, similarity estimation, and classification, while the broader survey also covers cognitive computing and architectures. These application areas are organized into finer clusters.

  • HDC/VSA applications are aggregated into deterministic behavior, similarity estimation, and classification for this application-focused section.

2.1 Deterministic behavior with HDC/VSA

HDC/VSA supports deterministic or approximately deterministic representations and behaviors across automata, instructions, schemas, communications, and string processing. These applications rely on compositional hypervectors, binding, superposition, permutation, and unbinding, while design choices and capacity limit determinism.

  • Deterministic behavior with HDC/VSA: Deterministic behavior depends on hypervector dimensionality, the number of atomic hypervectors, and rules for constructing compositional hypervectors.
  • Finite-state automata and grammars: Finite-state automata encode states and input symbols as hypervectors, then represent the transition function by superposing bound current-state, input, and next-state components.
  • Finite-state automata and grammars: The next automaton state is recovered by querying the transition hypervector with the current state and input binding, applying inverse permutation, and using item memory to denoise the result.
  • Finite-state automata and grammars: HDC/VSA has been used to represent pushdown automata, context-free grammars, Turing machines, cellular automata, construction grammars, and general-purpose parsing.
  • Controllers, instructions, schemas: Robot behaviors, instructions, and schemas can be represented compositionally by binding sensor inputs or contexts to corresponding actions, results, or rules.
  • Communications: Communication applications exploit distributed hypervectors’ noise robustness for collective sensing, wireless sensor access, error correction, and low-signal-to-noise communication.
  • Communications: A confidence-aware decoding method improved signal-to-noise ratio gain by 0.2 dB at a bit-error-rate of 10^-4 and was extended to several communication settings.
  • String processing: DNA string matching represents n-grams in compositional hypervectors and detects query presence when similarity exceeds a threshold controlling the true-positive and false-positive balance.

2.2 Similarity estimation with HVs

HDC/VSA represents application-relevant similarity in high-dimensional vectors, supporting similarity-based reasoning across linguistic, signal, image, and other data. Context-vector methods, especially RI and BEAGLE, provide influential approaches for semantic representation, while applications extend to biomedical synchronization, brain-region identification, and image aggregation.

  • HDC/VSA transformations preserve application-relevant similarity, enabling similarity search, classification, and analogical reasoning.The survey organizes similarity estimation around constructing high-dimensional representations from transformed input data.
  • Context vectors: Context HVs encode frequency distributions over defined objects and contexts, allowing the approach to be applied across domains.The survey focuses on context-vector methods commonly attributed to HDC/VSA.
  • Context vectors: Random Indexing and BEAGLE are the two most influential HDC/VSA methods for constructing word context vectors.RI uses sparse random projection, whereas BEAGLE uses HRR-based representations of word n-grams and context.
  • Context vectors: RI and BEAGLE achieved similar results on semantic tasks, while RI was much faster because it avoids circular convolution.A modified BEAGLE using random permutations was reported as more scalable and as providing better fits to semantic similarity than the circular-convolution version.
  • Applications: HDC/VSA similarity methods were applied to biomedical signals, iEEG-based seizure-region identification, and aggregated image descriptors.Aggregated image HVs generally outperformed alternative aggregation methods except exhaustive pair-wise comparison.

2.3 Classification

Classification is one of the most common HDC/VSA application areas, spanning languages, texts, acoustic and biomedical signals, automotive and behavioral data, images, and structured data. The survey also identifies uneven coverage: fault-classification studies are limited, while structured-data classification remains uncommon despite HDC/VSA's ability to represent hierarchies.

  • Classification is one of the most common HDC/VSA application areas because similarity-based and vector-based classifiers are widespread.The survey organizes classification studies first by input-data type and then by application domain.
  • Application domains: Language, text, acoustic, automotive, behavioral, biomedical, image, and structured-data classification are represented across the surveyed applications.The biomedical categories include EMG, EEG, CTG, DNA sequences, and SELDI-TOF mass spectrometry.
  • Fault classification: Fault-classification studies are limited to two identified use cases involving anomaly detection in a power plant and ball bearings.An earlier micro machine-tool acoustic-diagnostics work is also noted.
  • The survey tables deliberately omit in-depth data-transformation details and specify only the HDC/VSA operations used to construct HVs.This choice was made for generality.
  • Images: HVs for image classification were produced from extracted image features or from neural-network-derived HVs because raw pixels rarely performed well directly.The survey summarizes image-classification studies and their properties in Table 15.
  • Structured data: Structured-data classification is difficult for conventional vector classifiers when local representations involve hierarchies, whereas HDC/VSA can represent such structures as HVs.Despite this suitability, the survey reports very few structured-data studies.

3 COGNITIVE COMPUTING AND ARCHITECTURES

The survey treats cognitive computing and cognitive architectures as distinct from other application areas because they pursue different kinds of tasks. The supplied material identifies dedicated tables for image and structured-data classification but does not provide substantive cognitive-computing findings.

  • Cognitive computing and cognitive architectures are reviewed separately because their tasks differ from those in the survey's other application areas.
  • The supplied material includes an overview table for HDC/VSA studies classifying visual images and their properties.
  • The supplied material includes an overview table for HDC/VSA studies classifying structured data.

3.1 Cognitive computing

HDC/VSA supports cognitive computing through holistic transformations, analogical reasoning, logical inference, and models of human cognition. Applications demonstrate useful performance and behavioral similarity, while analogical mapping still lacks interaction and competition among alternative mappings.

  • Holistic transformations: Holistic transformation uses geometric properties of hypervector space as a parallel alternative to conventional sequential search.It transforms whole representations without decomposing them into individual symbolic components.
  • Analogical reasoning: HDC/VSA analogical retrieval uses hypervector similarity in a single stage and produces results consistent with psychological experiments and traditional models.The approach avoids the traditional two-stage retrieval-and-mapping process because similarity estimation is computationally inexpensive.
  • Analogical reasoning: SBDR analogical retrieval increased recall and noticeably increased precision relative to leading traditional two-stage models, with computational advantages in most cases.These results were obtained on test bases used by advanced analogical-retrieval models.
  • Analogical reasoning: Current HDC/VSA analogical-mapping models lack interaction and competition among consistent alternative mappings.An associative-memory approach was suggested as a possible improvement.
  • Cognitive modeling: HDC/VSA models cognitive abilities including sequence memory, Raven’s Progressive Matrices, Tower of Hanoi solving, and deductive inference.Sequence representations reproduced human memory findings; Tower of Hanoi response-time delays were qualitatively similar to human delays; other systems solved limited matrix tasks and logical-inference problems.

3.2 Cognitive architectures

HDC/VSA supports cognitive architectures by representing heterogeneous, hierarchical models and memories with hypervectors. Proposals include Spaun, APNNs, memory systems, and connections to other cognitive architectures, but several APNN aspects remain unresolved.

  • HDC/VSA has been used as an important component of several bio-inspired cognitive architectures.
  • Spaun: Spaun uses HRR-based hypervectors as semantic pointers within a 2.5-million-neuron spiking neural network.
  • Associative-Projective Neural Networks: APNNs use SBDR to construct hierarchical world models spanning sensory and abstract modalities and heterogeneous data types.
  • Associative-Projective Neural Networks: SBDR similarity search can recover both lower-level element hypervectors and higher-level compositional hypervectors.
  • Associative-Projective Neural Networks: APNN module memories use Hopfield-like auto-associative cleanup and form generalization hierarchies through correlated hypervectors, cores, and fringes.
  • Associative-Projective Neural Networks: APNN modeling remains incomplete, including unresolved questions about extracting hierarchical objects, assigning hierarchy levels, and representing transformation-invariant objects.
  • Other architectures and memories: Other proposals connect HDC/VSA with HTM, LIDA, MINERVA 2, and holographic declarative memory.

4.1 Application areas

HDC/VSA applications extend beyond classification, but effective use depends on feature extraction, data-to-hypervector transformations, classifier choice, and evidence of real-world scaling. Fractional power encoding is highlighted as a route to kernel-based and numeric-data applications.

  • Scope: Classification with HDC/VSA remains active, while important methodological aspects are often not addressed.
  • Hypervector formation: Meaningful feature extraction is usually required because directly transforming raw images or acoustic signals into hypervectors often performs poorly.
  • Hypervector formation: Data-to-hypervector transformations for classification are often ad hoc, with no straightforward general solution identified.
  • Hypervector formation: Nonlinear transformation can make originally nonlinearly separable classes linearly separable, but compositional hypervector nonlinearity remains insufficiently characterized.
  • Classifier choice: Centroids are computationally attractive but generally underperform weighted or learned alternatives such as perceptrons and support vector machines.
  • Classifier choice: Classifier compatibility depends on hypervector semantics: algorithms assuming independently meaningful components may fail, whereas sparsity-aware classifiers can be advantageous.
  • Beyond classification: Beyond classification, HDC/VSA has been applied to clustering, unsupervised, multi-task, distributed, compression, and ensemble learning.
  • Beyond classification: Fractional power encoding supports kernel approximations and numeric-data applications including probability estimation, dynamical systems, navigation, time series, and neuroscience.

4.2 Interplay with neural networks

HDC/VSA interfaces with neural networks by compactly representing high-dimensional or variable-size inputs, translating neural activations into hypervectors, and expressing randomized or spiking-network operations in HDC/VSA terms. These combinations can reduce network size, support neuromorphic implementations, and provide a programming abstraction for cognitive functionalities, but input transformations and some architectural choices remain challenging.

  • HVs as input to neural networks: High-dimensional sparse data can be encoded as compact hypervectors while preserving similar classification performance in smaller neural networks.Performance degradation is gradual as hypervector dimensionality decreases, allowing a tradeoff between network size and performance.
  • HVs as input to neural networks: Variable-size inputs can be converted into fixed-size hypervectors before entering neural networks.Demonstrations include representing varying intersections crossed by a vehicle and dynamically changing automotive environments.
  • Architectural trade-offs: The variable-size interface may broaden neural-network applicability but can require replacing widely used convolutional layers.The survey notes fully connected networks as a possible alternative even for vision tasks.
  • Learning and transformation: Transforming unstructured data such as images into hypervectors is non-trivial, and these transformations are usually not learned.This motivates converting neural-network activations into hypervectors instead.
  • Randomized neural networks: HDC/VSA operations can express the randomness used in feed-forward and recurrent randomized neural networks, while capacity theory can explain reservoir memory characteristics and predict neural-network accuracy.The mapping extends HDC/VSA capacity analysis to architectures including deep convolutional neural networks.
  • Spiking neural networks: HDC/VSA maps readily to spiking activities through rate-based or phase-to-timing coding and has been used for associative memories, k-nearest-neighbor classifiers, and unsupervised-learning pipelines on spiking neural networks.These applications provide initial evidence of HDC/VSA expressiveness and compatibility with spiking neural networks.

4.3 Open issues

The survey identifies open issues spanning representation, memory, learning, similarity, parsing, hierarchy, causality, and symbolic interfaces. Although HDC/VSA offers unified multimodal representations and compositionality, progress is limited by difficult input transformations, incomplete neural integration, and unresolved mechanisms for generalization and structured reasoning.

  • Representation and compositionality: HDC/VSA uses a unified hypervector format across data types and modalities, with operations that introduce compositionality when input representations specify structure explicitly.The required compositional structure is not always available in the input representation.
  • Learning: Most existing work reimplements symbolic or machine-learning primitives with hypervectors, while learning is used mainly to train classifiers on already constructed representations.Learning transformations from data into hypervectors remains relatively rare.
  • Applications and efficiency: Comparable state-of-the-art results on simple classification and similarity-search problems can require only a fraction of baseline energy or computational costs.These results suggest possible niches in tiny machine learning and edge machine learning, while learned hypervector formation remains limited.
  • Neural integration: Few efforts establish general principles for combining neural networks and HDC/VSA, despite the relevance of such combinations to connectionist artificial intelligence.Existing proposals introduce Tensor Product Representation or HDC/VSA operations into neural-network machinery.
  • Compositionality: Binding supports compositionality without training, but its neural implementation in spiking neural networks remains an open issue.Two recent proposals aim to address this implementation problem.
  • Generalization and reasoning: Analogical reasoning could support compositionality and causal-dependency discovery, but building analogical episodes and part-whole or is-a hierarchies remains insufficiently studied.The survey points to associative memories and learned image parsing as possible directions.
  • Recovery and memory: Recovery of element hypervectors is often combinatorial because most models require knowledge of all but one bound hypervector.Resonator-network proposals address factorization problems associated with recovery.
  • Similarity: Binding can destroy similarity when one input hypervector differs, potentially hindering similarity search across slightly different combinations.This trade-off arises because dissimilarity from inputs is often convenient or desired.

5 CONCLUSION

The two-part survey comprehensively covers HDC/VSA models, input transformations, applications, cognitive modeling, architectures, open problems, and future directions. It is intended to guide newcomers, broaden practitioners’ perspectives, and support convergence toward common terminology and stronger theoretical foundations.

  • Scope: Part II surveys HDC/VSA applications, cognitive modeling, cognitive architectures, open problems, and promising future directions.Part I covered existing models and transformations of varied input data into distributed representations.
  • Audience and purpose: The survey aims to guide newcomers and broaden practitioners’ views beyond their specializations.It also seeks to facilitate exploration and identify fruitful directions for research and exploitation.
  • Field development: The authors expect the two-part survey to accelerate convergence toward common terminology and solid theoretical foundations in HDC/VSA.
Loading 2112.15424v3…