Computing with Residue Numbers in High-Dimensional Representation

Christopher J. Kymn, Denis Kleyko, Edward Paxon Frady, Connor Bybee, Pentti Kanerva, Friedrich T. Sommer, Bruno A. OlshausenNeural Computation 2023 · DOI · OpenReview

TL;DR

This paper introduces Residue Hyperdimensional Computing (RHC), a novel framework that unifies residue number systems with high-dimensional vector representations. RHC enables efficient, parallelizable computation on numerical values with a large dynamic range, offering significant advantages in memory and processing power compared to existing methods, while also demonstrating impressive robustness to noise.

What Problem Does This Paper Address?

Representing and computing with numerical values (like position, velocity, etc.) is fundamental to both machine learning and computational neuroscience. Traditional methods often struggle with large dynamic ranges, requiring significant memory and computational resources. In neuroscience, the "grid cell" system in the brain, which encodes spatial location with remarkable efficiency, has been linked to residue number systems. This paper aims to bridge this gap by developing a computational framework that leverages the strengths of both residue number systems and hyperdimensional computing to achieve efficient, robust, and scalable numerical computation.

Methods

The core of this work is the Residue Hyperdimensional Computing (RHC) framework. It builds upon Fractional Power Encoding (FPE), a technique that maps numbers to high-dimensional vectors. The key innovations are:

  • Residue Modulo Encoding: FPE is adapted to represent numbers modulo specific integers (residue number system). This is achieved by constraining the random phases in FPE to be roots of unity. This allows for algebraic operations to be performed component-wise on the high-dimensional vectors, mirroring the carry-free arithmetic of residue number systems.
  • Two Binding Operations: RHC introduces two distinct operations for combining vectors:
  • Hadamard product (⊙): Implements vector addition, corresponding to addition of the encoded numbers.
  • Multiplicative binding (⋆): Implements vector multiplication, corresponding to multiplication of the encoded numbers. This is a novel contribution to hyperdimensional computing.
  • Resonator Network for Decoding: The paper utilizes a "resonator network" for efficient decoding of these high-dimensional representations back into numerical values. This network is shown to be significantly faster and more memory-efficient than traditional codebook decoding methods, especially for large effective ranges.
  • Hexagonal Coordinate Systems: The framework is extended to represent multi-dimensional spaces, including hexagonal coordinate systems, which are inspired by grid cell representations and offer higher coding resolution than Cartesian systems.

Datasets

The paper does not explicitly mention specific datasets used for training or evaluation in the traditional machine learning sense. Instead, it focuses on demonstrating the framework's capabilities through simulations and analyses on synthetic problems, such as:

  • Visual Scene Disentangling: A simplified problem involving disentangling object identity, horizontal position, and vertical position from images. This uses MNIST digits as a basis for object representation.
  • Subset Sum Problem: A combinatorial optimization problem used to test the framework's ability to find exact solutions.

Key Insights and Ideas

  • Bridging Number Systems and HDC: The most significant insight is the successful unification of residue number systems with hyperdimensional computing. This combination unlocks the benefits of both: the algebraic efficiency of RNS and the robustness and distributed nature of HDC.
  • Carry-Free Arithmetic in HDC: RHC enables carry-free arithmetic (addition, subtraction, multiplication) directly on high-dimensional vectors, a property that is crucial for efficient computation.
  • Efficient Decoding is Key: The development and application of the resonator network for decoding are critical. It demonstrates that the computational advantages of RHC are not just in encoding but also in retrieving the original information efficiently.
  • Biological Plausibility: The framework offers a potential computational account for grid cell representations in the brain, suggesting how these neurons might implement efficient spatial coding.
  • Novel Algebraic Operations: The introduction of two distinct binding operations (addition and multiplication) for vector representations is a key theoretical advancement.

Key Results

  • Memory and Computation Savings: RHC significantly reduces memory requirements and computational overhead for decoding compared to standard hyperdimensional computing methods. For instance, in the visual scene disentangling task, RHC reduced codebook vectors from 220 to 40 and average codebook evaluations from ~2000 to ~800.
  • Efficient Subset Sum Solving: The framework successfully finds exact solutions to the subset sum problem, outperforming brute-force search and showing competitive performance against exact solvers, especially for larger problem sizes.
  • Robustness to Noise: The resonator network decoding mechanism demonstrates remarkable robustness to phase noise, maintaining high accuracy even under noisy conditions.
  • Improved Spatial Resolution: The implementation of hexagonal coordinate systems in RHC provides higher spatial resolution compared to square lattices for the same computational resources.

Limitations and Future Work

  • Division is Not Well-Defined: Similar to standard residue number systems, division is not directly supported in RHC, although multiplications by non-zero integers are invertible when moduli are prime.
  • Sub-Integer Precision Challenges: While RHC can be extended to handle rational numbers, multiplication becomes less straightforward, and decoding sub-integer values is sensitive to phase noise.
  • Hardware Implementation: The authors suggest that further performance gains could be achieved by implementing the resonator network on emerging computing platforms.
  • Broader Applications: The framework's potential for solving complex combinatorial optimization problems and modeling neural computations warrants further exploration. The authors propose that each grid cell module could correspond to a factor estimate in the resonator network, suggesting a new direction for systems neuroscience research.

Summary updated

Abstract

We introduce Residue Hyperdimensional Computing, a computing framework that unifies residue number systems with an algebra defined over random, high-dimensional vectors. We show how residue numbers can be represented as high-dimensional vectors in a manner that allows algebraic operations to be performed with component-wise, parallelizable operations on the vector elements. The resulting framework, when combined with an efficient method for factorizing high-dimensional vectors, can represent and operate on numerical values over a large dynamic range using vastly fewer resources than previous methods, and it exhibits impressive robustness to noise. We demonstrate the potential for this framework to solve computationally difficult problems in visual perception and combinatorial optimization, showing improvement over baseline methods. More broadly, the framework provides a possible account for the computational operations of grid cells in the brain, and it suggests new machine learning architectures for representing and manipulating numerical data.
BibTeX
@article{kymn2023computing,
  author = {Christopher J. Kymn and Denis Kleyko and Edward Paxon Frady and Connor Bybee and Pentti Kanerva and Friedrich T. Sommer and Bruno A. Olshausen},
  title = {{Computing with Residue Numbers in High-Dimensional Representation}},
  journal = {Neural Computation},
  year = {2023},
  doi = {10.1162/neco\_a\_01723},
}
Figure