PaperlayerView exact revision on arXiv

Source-linked AI summary

A Survey on Hyperdimensional Computing aka Vector Symbolic Architectures, Part I: Models and Data Transformations

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

arXiv:2111.06077v2cs.AIcs.LG

TL;DR

HDC/VSA research is broad and fragmented across disciplines, creating a need for a comprehensive account of its models and representations. This Part I surveys foundational models and input transformations, showing how binding and superposition address challenges in distributed representations while noting unresolved theoretical questions.

  • Problem

    Prior HDC/VSA work is dispersed across venues and disciplines, and distributed representations face challenges including superposition catastrophe, systematicity, and fast compositionality.

  • Method

    The survey comprehensively covers HDC/VSA models, foundational operations, and transformations of varied input data into hypervector representations.

  • Results

    Binding and superposition yield similar distributed representations for similar compositional objects, while capacity theory predicts sequence-retrieval accuracy very accurately for BSC, MAP, and FHRR.

  • Takeaways & Limitations

    HDC/VSA provides a family of fixed-dimensional, high-dimensional distributed representations that combine symbolic structure with connectionist vector representations.

  • Takeaways & Limitations

    There is no agreement on a canonical binding definition, and the survey leaves connections to other fields and hardware implementations outside its scope.

Abstract

from arXiv · show

This two-part comprehensive survey is 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. Notable models in the HDC/VSA family are Tensor Product Representations, Holographic Reduced Representations, Multiply-Add-Permute, Binary Spatter Codes, and Sparse Binary Distributed Representations but there are other models too. HDC/VSA is a highly interdisciplinary field with connections to computer science, electrical engineering, artificial intelligence, mathematics, and cognitive science. This fact makes it challenging to create a thorough overview of the field. However, due to a surge of new researchers joining the field in recent years, the necessity for a comprehensive survey of the field has become extremely important. Therefore, amongst other aspects of the field, this Part I surveys important aspects such as: known computational models of HDC/VSA and transformations of various input data types to high-dimensional distributed representations. Part II of this survey is devoted to applications, cognitive computing and architectures, as well as directions for future work. The survey is written to be useful for both newcomers and practitioners.

1 INTRODUCTION

HDC/VSA is a family of high-dimensional vector frameworks positioned between symbolic AI and connectionism. This survey addresses the field’s fragmented literature through broad coverage of its models, representations, and data transformations.

  • HDC/VSA combines structured symbolic representations with the advantages of connectionist vector distributed representations.The framework uses hypervectors and mathematical properties of high-dimensional vector spaces.
  • The field has gained momentum through dissemination, successful engineering applications, cognitive architectures, and interest in alternatives to conventional computing.
  • The survey responds to literature dispersed across venues and disciplines, which makes the field’s state of the art difficult to track.
  • No previous work had attempted a comprehensive survey of HDC/VSA, although earlier articles covered particular topics.
  • Part I covers HDC/VSA motivation, basic notions, known models, transformations of data into hypervectors, discussion, and conclusions.Applications and cognitive architectures are reserved for Part II.
  • Connections with other research fields and hardware implementations remain outside this survey’s scope because of space limitations.

2 HYPERDIMENSIONAL COMPUTING AKA VECTOR SYMBOLIC ARCHITECTURES

This section introduces the motivation, components, models, and information capacity underlying HDC/VSA. It organizes these foundations before the survey turns to data transformations.

  • The section reviews motivations for early HDC/VSA models, lists their components, overviews existing models, and discusses hypervector information capacity.

2.1 Motivation and basic notions

HDC/VSA arose to combine symbolic structure with distributed representations while addressing limitations of conventional symbolic, localist, and early distributed approaches. Its binding and superposition operations support compositional representations that preserve similarity and fixed dimensionality.

  • 2.1.1 Types of representation: Symbolic representations provide explicit combinatorial structure but similarity search and reasoning can require complex sequential operations that become intractable with scale.
  • 2.1.1 Types of representation: Conventional symbolic computation also assumes reliable hardware, making biological implementation difficult when computational errors can cause fatal faults.
  • 2.1.1 Types of representation: Localist representations associate each object with one element, but compositional combinations require potentially unbounded new elements and connections.
  • 2.1.1 Types of representation: Distributed representations encode objects across vector components, whose individual semantics are generally undefined without the states of other components.
  • 2.1.1 Types of representation: Useful distributed representations should support high capacity, explicit similarity, rich semantic bases, vector processing, recovery, noise tolerance, and direct access.
  • 2.1.2 Challenges for conventional connectionist representations: Early distributed representations faced superposition catastrophe, systematicity, and fast-compositionality challenges, motivating structure-sensitive binding.
  • 2.1.3 Binding to address challenges of conventional connectionist representations: HDC/VSA binding preserves representation dimensionality and requires no training, unlike earlier approaches that could increase dimensionality.
  • 2.1.3 Binding to address challenges of conventional connectionist representations: Binding and superposition produce similar distributed representations for similar compositional objects while incorporating elements, grouping, and order.

2.2 Structure-sensitive distributed representations

HDC/VSA assigns high-dimensional vectors to basic objects so similarity can encode desired relationships, then combines them through superposition and binding to represent structured compositions. Superposition preserves similarity but can erase grouping, motivating binding and later unbinding or clean-up operations.

  • Atomic representations: Atomic HVs represent basic objects, with their similarity chosen to reflect the properties relevant to the problem.Component values may be binary, real, or complex.
  • Atomic representations: Random quasi-orthogonal HVs can represent many dissimilar symbols at fixed dimensionality, accommodating N symbols with D-dimensional HVs where N >> D.This capacity follows from the exponential number of quasi-orthogonal directions in high-dimensional spaces.
  • Superposition: Superposition forms an HV for several inputs through disjunction or addition, often followed by normalization to preserve desired norm or component constraints.Implementations include binary majority rules, range-limiting functions, and sparsity-preserving thinning.
  • Superposition: Superposition remains similar to its inputs, but similarity decreases as more HVs are combined; its standard form is associative.Associativity makes the sum independent of component order.
  • Binding: Recursive superposition loses information about object groupings, so binding is used to represent compositional structure through multiplication-like or permutation operations.Binding produces a result dependent on all inputs, while similar inputs generally yield similar bound HVs.
  • Binding: Unbinding reverses binding to recover a constituent HV, typically producing noise that is resolved through a clean-up procedure and item memory.The recovered signal is selected as the closest match under an appropriate similarity measure.

2.3 The HDC/VSA models

HDC/VSA models differ because independent research traditions made different assumptions about representations and operations, so model choice is historically ill-posed but can be guided by target hardware. The survey compares model-specific HV formats, binding and superposition operations, and similarity measures across established models.

  • Overview: The survey overviews HDC/VSA models by comparing their HV formats, basic binding and superposition operations, and similarity measures.Table 2 summarizes these model-specific choices.
  • Model diversity: Model diversity reflects independent historical development, differing initial assumptions, neurobiological inspirations, and mathematical backgrounds.Consequently, selecting a universally best model is ill-posed from a historical perspective.
  • Hardware perspective: Target computing hardware can already guide model prioritization because HDC/VSA is relevant to energy-efficient and reliable unconventional hardware.The framework is described as promising for hardware that is inherently unreliable or unsuitable for conventional von Neumann architectures.
  • Tensor Product Representations: TPR uses random unit-sphere atomic HVs, tensor addition for superposition, and tensor-product binding whose dimensionality grows with composition.Recursive binding is challenging because the dimensionality grows, and the resultant tensor depends on presentation order.
  • Holographic Reduced Representations: HRR uses real-valued random HVs, circular convolution for binding, component-wise addition for superposition, and correlation-based unbinding followed by clean-up.Both binding and superposition are commutative in HRR.
  • Binary Spatter Codes: BSC uses dense binary HVs, majority-thresholded addition for superposition, and component-wise XOR for binding.BSC can be viewed as a special case of FHRR with angles restricted to 0 and π.

2.3.8 Sparse Binary Distributed Representations

Sparse Binary Distributed Representations use sparse binary hypervectors with conjunction or Context-Dependent Thinning binding, preserving similarity that supports recovery through similarity search. Related sparse or integer-valued models vary their block structure, binding, superposition, and similarity operations.

  • Sparse Binary Distributed Representations: SBDR uses binary hypervectors with Conjunction and Context-Dependent Thinning as two binding variants.SBDR emerged from Associative-Projective Neural Networks, and Context-Dependent Thinning was previously called normalization.
  • Sparse Binary Distributed Representations: Conjunction binds binary hypervectors component-wise, while disjunction superposes them and preserves structured similarity.The operations are commutative, although random permutations can represent argument order.
  • Sparse Binary Distributed Representations: Context-Dependent Thinning first superposes inputs, then permutes and conjuncts the result, and finally disjunctively superposes T such bindings.The number of permutation-disjunctions T controls resultant density; increasing T eventually removes binding effects.
  • Sparse Binary Distributed Representations: SBDR binding preserves unstructured similarity, making bound results similar to their inputs and enabling recovery through similarity search in item memory.This distinguishes SBDR from multiplicative binding schemes where corresponding bound results are generally dissimilar.
  • Sparse Block Codes: Sparse Block Codes partition sparse binary hypervectors into equal blocks containing one active component, and bind them with block-wise circular convolution.With maximally sparse blocks, binding is equivalent to adding corresponding indices modulo the block size; superposition uses component-wise addition and may be binarized per block.
  • Integer-Valued Models: MCR uses integer-valued hypervectors with modular-addition binding and modular-subtraction unbinding, while CGR provides a related integer-valued model with different similarity and superposition definitions.MCR interprets integers as discretized phase angles and normalizes superpositions to the nearest allowed phase.
  • Geometric Analogue of Holographic Reduced Representations: GAHRR reformulates HRR using geometric algebra, but its advantages over simpler models remain unclear and its relevance is mainly theoretical so far.The survey notes that GAHRR could become more relevant in the future.

2.4 Information capacity of HVs

Information capacity measures how much information can be stored and recovered from superposed hypervectors, with accuracy depending on item-memory and distribution parameters. Capacity theory provides analytical retrieval predictions that closely match empirical sequence-recovery accuracies across several HDC/VSA models.

  • Capacity Definition: Information capacity asks how much information can be stored in a superposition of hypervectors, typically representing a set of random, dissimilar symbols.Capacity depends on parameters including the number of symbols in item memory.
  • Capacity Theory: Capacity theory computes expected retrieval accuracy from the means and standard deviations of the target and recovered-item distributions, with item-memory size N entering the formula.The cumulative Gaussian Φ and item-memory size N are used in the analytical expression.
  • Empirical Validation: Analytical capacity predictions accurately match empirical sequence-element retrieval for BSC, MAP, and FHRR.The comparison uses accuracies retrieved from compositional hypervectors.
  • Extensions: Capacity theory has been extended to classification, while other studies provide bounds, empirical analyses, and methods for recovering information from hypervectors.The cited work spans classification accuracy, perfect retrieval of sets and sequences, and analytical capacity results.
  • Decoding Improvements: Redundant storage can improve decoding by averaging noise across multiple copies of the same data derived from different permutations.The multiset intersection circuit is presented as an example of this strategy.

3 DATA TRANSFORMATION TO HVS

HDC/VSA transforms diverse data types into hypervectors to create distributed representations whose simple vector similarities can support structural comparison. Part I covers transformations for symbols, sets, role-filler bindings, numeric data, sequences, images, and graphs.

  • Motivation: HDC/VSA uses vector representations and simple vector similarity measures to compare structured data such as sequences and graphs.This contrasts with computationally expensive procedures such as edit distance used for some symbolic structures.
  • Scope: The survey covers transformations of symbols, sets, role-filler bindings, numeric scalars and vectors, sequences, 2D images, and graphs into hypervectors.These transformations are organized across Sections 3.1 through 3.5.

3.1 Symbols and Sets

Symbols are commonly mapped to independent random hypervectors, while sets are represented by superposing the hypervectors of their members. Structured role-filler records use binding, and sets of such bindings use superposition subject to capacity limits.

  • Symbols: Different symbols are typically transformed into independent, identically distributed random hypervectors that are maximally similar to copies and minimally similar to one another.This preserves the all-or-none behavior of symbolic identity and difference.
  • Sets: In localist representations, sets use characteristic vectors, with components indicating symbol presence and multiset components storing symbol counts.Each component corresponds to a symbol in the universe.
  • Sets: HDC/VSA usually represents a set by superposing its members’ hypervectors, preserving similarity to those members.A binary-disjunction Bloom filter is described as a special case of this representation, whereas multiplicative bindings have different similarity properties.
  • Role-Filler Bindings: Role-filler bindings represent structured records by binding role and filler hypervectors, using either multiplicative binding or binding by permutation.Multiplicative binding can represent associations involving more than two hypervectors, such as context, action, and result.
  • Role-Filler Bindings: A set of role-filler bindings is represented by superposing their hypervectors, but the number superposed must remain limited to preserve recoverable information.The limit is tied to the ability to recover the constituent hypervectors.

3.2 Numeric scalars and vectors

HDC/VSA transforms numeric scalars and vectors into high-dimensional representations while preserving useful similarity relationships. The survey distinguishes compositional, receptive-field, and random-projection approaches, each with different encoding assumptions and flexibility.

  • Design requirements: Numeric encodings should make nearby scalar values produce similar HVs and distant values produce dissimilar HVs.Random independent HVs do not preserve similarity between close numeric values.
  • Compositional approach: Scalar compositional schemes normalize and quantize values into levels, using correlated HVs whose similarity decreases with value difference.Earlier methods generate intermediate grade HVs through interpolation or component changes.
  • Compositional approach: Fractional power encoding represents scalars by exponentiating a random base HV, with bandwidth β controlling the similarity-kernel width.It avoids preset-range normalization and quantization and applies to FHRR and suitably phase-resolved representations.
  • Compositional approach: Compositional vector encoding first represents scalar components, then combines their HVs through superposition or binding.Scalar values from different components should remain dissimilar so component–value associations are preserved.
  • Random projections: Random projections form z = Rx and may then normalize, binarize, or sparsify the result using matrices with several possible component distributions.The approach supports arbitrary input dimensionality and numbers of component gradations, unlike compositional and receptive-field approaches.
  • Random projections: Random-projection representations encode numeric vectors through weighted superpositions of matrix columns, rather than scalar similarity encoded by HV direction.Multiple projection matrices can also be combined with weights λ_i.

3.3 Sequences

HDC/VSA represents sequences by associating symbols with positions or contexts and then combining the resulting HVs. Superposition supports sequence similarity, whereas binding can distinguish sequences differing at a single position.

  • Sequence encoding: Standard sequence encodings bind symbol HVs with position HVs, use permutations, bind with context HVs, or represent n-grams.These approaches provide alternative ways to encode order and local context.
  • Position and context: Correlated position HVs preserve similarity between symbols in nearby positions, so shifted sequences can remain similar.Context binding instead associates each symbol with the HV of one or more preceding symbols.
  • Superposition: Superposition combines position-associated symbol HVs into one sequence HV whose similarity can be compared with another sequence HV.For (a,b,c,d,e), the representation is s = ρ0(a) + ρ1(b) + ρ2(c) + ρ3(d) + ρ4(e).
  • Binding: Binding permuted HVs can produce quasi-orthogonal representations even when two sequences differ in only one position.The current sequence HV can be extended with fixed computational cost per added symbol.
  • N-grams: N-gram encodings extract consecutive symbol groups and can superpose their HVs, distinguishing symbol identity and order while retaining similarity for similar n-grams.Compositional n-gram HVs avoid storing an atomic HV for every possible n-gram.

3.4 2D images

HDC/VSA represents 2D images by encoding pixel values together with spatial positions through permutations, role-filler bindings, fractional power encoding, or neural-network features. The survey emphasizes that direct pixel-to-HV transformations may underperform unless the encoder captures task-relevant information.

  • Representation families: 2D-image representations fall into permutation-based, role-filler binding-based, and neural-network-based groups, with some hybrid proposals.One hybrid example combines pixel flattening, normalization, permutation, and circular-convolution binding.
  • Permutation-based representations: Permutation-based image encodings assign separate transformations to x- and y-coordinates and superpose position-encoded pixel-value HVs.Cyclic shifts and tensor restructuring can implement orthogonal spatial shifts.
  • Permutation-based representations: Partial permutations make nearby pixel positions increasingly dissimilar within a radius, then repeat the process beyond that radius.This addresses the absence of local similarity in fully permutation-based representations.
  • Role-filler representations: Role-filler image encodings bind each pixel’s position HV with its value HV and superpose the resulting bindings.Unique random position HVs are simple but impose no relations between pixel positions.
  • Fractional power encoding: Fractional power encoding uses two random base HVs exponentiated to x and y coordinates, then binds the result with the pixel value HV.It imposes spatial structure and can preserve local-neighborhood similarity.
  • Neural-network-based representations: Direct pixel-to-HV image encodings on MNIST reported lower accuracy than pixel-space kNN or a simple two-layer neural network.Feature extraction or neural-network front ends are therefore used to produce more task-relevant HVs.
  • Neural-network-based representations: Designed neural networks can produce quasi-orthogonal class HVs that support few-shot continual learning with small interference and state-of-the-art classification accuracy.The survey notes that different neural-network architectures have not yet been systematically compared for HV generation.

3.5 Graphs

HDC/VSA represents graphs by assigning HVs to nodes and encoding edges or labelled relations through binding, permutation, and superposition. These constructions support recovery and similarity comparisons while extending to directed, labelled, ordered, and knowledge graphs.

  • Basic graph representations: An undirected graph can be represented by superposing bindings of HVs assigned to connected node pairs.For example, g = a ◦b + a ◦e + b ◦c + c ◦d + d ◦e.
  • Basic graph representations: Directed edges encode direction by permuting the HV of the destination node before binding it with the source HV.The directed representation uses terms such as a ◦ρ(b) for an edge from a to b.
  • Basic graph representations: Graph elements can be recovered with item memory, and dot products measure overlapping edges when graphs share node HVs.The basic representation omits isolated vertices unless vertex and edge sets are represented separately.
  • Labelled directed graphs: Labelled directed graphs can compose predicate, entity, argument-role, and relation-role HVs into nested representations.The example encodes bite(Spot,Jane) and cause(bite(Spot,Jane),flee(Jane,Spot)).
  • Labelled directed graphs: SBDR forms a more compact labelled-graph representation because its binding preserves unstructured similarity.HRR and BSC retain similarity between resultant graph HVs and their various elements through binding properties.
  • Labelled directed graphs: Predicate–argument relations can represent argument order by applying distinct random permutations to role-associated entity HVs.The BITE example uses ρagent(spot) and ρobject(jane).
  • Knowledge graphs: Knowledge-graph HVs have achieved state-of-the-art missing-link inference when supplied to a neural network, and learned node and relation HVs have also been proposed.One approach uses Cauchy-distributed atomic HVs, while another uses differentiable HRR representations.
  • Trees: Trees are graph instances and can therefore use the same HV transformations, with separate proposals for unordered and ordered binary trees.Tree representations have also been studied for Tensor Product Representations using cryptographic hashing.

4 DISCUSSION

The discussion identifies unresolved theoretical questions in HDC/VSA, including model relationships, binding definitions, and principled capacity and reconstruction guarantees. It also highlights the framework’s suitability for unconventional hardware implementations.

  • Theoretical foundations: Connections between HDC/VSA models remain incompletely understood, particularly when comparing component-interacting and component-wise multiplicative binding operations.The survey distinguishes models using interactions among multiple hypervector components from models applying multiplicative binding component-wise.
  • Theoretical foundations: No single HDC/VSA model is known to dominate across applicability, mathematical properties, information capacity, and noise robustness.The survey calls for continued systematic comparisons among models across these dimensions.
  • Theoretical foundations: HDC/VSA has largely developed empirically while implicitly relying on concentration of measure and random projection.The discussion presents these mathematical phenomena as part of the field’s underlying foundations.
  • Theoretical foundations: HDC/VSA needs stronger theoretical foundations, including capacity estimates and guarantees for reconstructing data structures from hypervectors.Recent work has begun addressing these needs through capacity theory and upper-bound guarantees.
  • Theoretical foundations: There is no agreed canonical definition of binding, including whether binding should produce dissimilar results or preserve similarity to its arguments.Existing proposals have been taxonomized, but the abstract definition and practical value of deviations remain open questions.
  • Hardware: HDC/VSA is promising for neuromorphic, in-memory, and monolithic 3D integration hardware implementations.The suitability of the framework for unconventional hardware has motivated specialized implementations since the field’s early development.

5 CONCLUSION

Part I provides comprehensive coverage of HDC/VSA models and transformations from diverse input data types into hypervector representations. Part II extends the survey to applications, cognitive architectures, and future research directions.

  • 5 CONCLUSION: Part I comprehensively surveys HDC/VSA models and transformations of various input data types into hypervector representations.Its coverage focuses on the computing framework’s model family and data-to-hypervector transformations.
  • 5 CONCLUSION: Part II reviews applications, cognitive modeling and architectures, open problems, and promising directions for future work.The second part complements Part I by addressing uses and broader research directions.
Loading 2111.06077v2…