A Theoretical Perspective on Hyperdimensional Computing (Extended Abstract)

1 Introduction

Hyperdimensional (HD) computing is an emerging area at the intersection of computer architecture and theoretical neuroscience [Kanerva, 2009]. It is based on the observation that brains are able to perform complex tasks using circuitry that: (1) uses low power, (2) requires low precision, and (3) is highly robust to data corruption. HD computing aims to carry over similar design principles to a new generation of digital devices that are highly energy-efficient, fault tolerant, and well-suited to natural information processing [Rahimi et al., 2018].

The wealth of recent work on neural networks also draws its inspiration from the brain, but modern instantiations of these methods have diverged from the desiderata above. The success of these networks has rested upon choices that are not neurally plausible, most notably significant depth and training via backpropagation. Moreover, from a practical perspective, training these models often requires high precision and substantial amounts of energy. While a large body of literature has sought to ameliorate these issues with neural networks, these efforts have largely been designed to address specific performance limitations. By contrast, the properties above emerge naturally from the basic architecture of HD computing.

∗ Published in the Journal of Artificial Intelligence Research (JAIR)

Hyperdimensional computing focuses on the very simplest neural architectures. Typically, there is a single, static, mapping from inputs x to much higher-dimensional "neural" representations ϕ(x) living in some space H. All computational tasks are performed in H-space, using simple, operations like element-wise additions and dot products. The mapping ϕ is often taken to be random, and the embeddings have coordinates that have low precision; for instance, they might take values -1 and +1. The entire setup is elementary and lends itself to fast, low-power hardware realizations.

Indeed, a cottage industry has emerged around developing optimized implementations of HD computing based algorithms on hardware accelerators [Imani et al., 2017; Rahimi et al., 2018; Gupta et al., 2018; Schmuck et al., 2019; Salamat et al., 2019; Imani et al., 2019]. Broadly speaking, this line of work touts HD computing as an energy efficient, low-latency, and noise-resilient alternative to conventional realizations of general purpose ML algorithms like support vector machines, multilayer perceptrons, and nearest-neighbor classifiers. While this work has reported impressive performance benefits, there has been relatively little formal treatment of HD computing as a tool for general purpose learning.

Our work has two broad aims. The first, more modest, goal is to introduce the area of hyperdimensional computing to a machine learning audience. The second is to develop a particular mathematical framework for understanding and analyzing these models. The recent literature has suggested a variety of different HD architectures that conform to the overall blueprint given above, but differ in many important details. We present a unified treatment of many such architectures that enables their properties to be compared. The most basic types of questions we wish to answer are:

1. How can individual items, sets of items, and sequences of items, be represented and stored in H-space, in a manner that permits reliable decoding?
2. What kinds of noise can be tolerated in H-space?
3. What kinds of structure in the input x-space are preserved by the mapping to H-space?
4. What is the power of linear separators on the ϕrepresentation?

Some of these questions have been introduced in the HD

computing literature and studied in isolation [Plate, 2003; Gallant and Okaywe, 2013; Kleyko et al., 2018; Frady et al., 2018]. In this work we address these questions formally and in greater generality.

2 Introduction to HDComputing

We being by providing an introduction to the fundamentals of HD computing and some brief discussion of its motivations in the neuroscience literature.

Neuroscience has proven to be a rich source of inspiration for the machine learning community: from the perceptron [Rosenblatt, 1958], which introduced a simple and general-purpose learning algorithm for linear classifiers, to neural networks [Rumelhart et al., 1986], to convolutional architectures inspired by visual cortex [Fukushima, 1980], to sparse coding [Olshausen and Field, 1996] and independent component analysis [Bell and Sejnowski, 1995]. One of the most consequential discoveries from the neuroscience community, underlying much research at the intersection of neuroscience and machine learning, has been the notion of high-dimensional distributed representations as the fundamental data structure for diverse types of information. In the neuroscience context, these representations are also typically sparse.

The notion of high-dimensional, distributed, data representations has engendered a number of computational models that have collectively come to be known as vector symbolic architectures (VSA) [Levy and Gayler, 2008]. In general, VSAs provide a systematic way to generate and manipulate high-dimensional representations of symbols so as to implement cognitive operations like association between related concepts. Notable examples of VSAs include "holographic reduced representations" [Plate, 1995; Plate, 2003], "binary spatter codes" [Kanerva, 1994; Kanerva, 1995], and "matrix binding of additive terms" [Gallant and Okaywe, 2013]. HD computing can be seen as a successor to these early VSA models, with a strong additional slant towards hardware and computational efficiency. While our treatment focuses primarily on recent work on HD computing, many of our results apply to these earlier VSA models as well.

An overview of data-flow in HD computing is given in Figure 1. The first step in HD computing is encoding, which maps a piece of input data to its high-dimensional representation under some function ϕ : X → H. The nature of ϕ depends on the type of input and the choice of H. The space H is some d-dimensional inner-product space defined over the real numbers or a subset thereof. For computational reasons, it is common to restrict H to be defined over integers in a limited range [-b, b].

The HD representations of data can be combined, using simple element-wise operators, to affect various information processing tasks. Two particularly important operators are "bundling" and "binding." The bundling operator is used to superimpose multiple HD representations into a single point. For instance, given a set of items S ⊂ X, one represents S by bundling together the encodings of constituent items: ϕ(S) = ⊕a∈Sϕ(a). The binding operator is used to construct representations of structured data in which points consists of feature-value pairs. For a feature f ∈ F taking on a value a ∈ X, its embedding is constructed as ψ(f) ⊗ ϕ(a). These representations can also typically be "decoded" to recover the atomic inputs. In addition to storing and recalling patterns, HDC can be used for learning problems like classification and regression. HDC learning techniques typically take the form of simple, linear (on the HD version of data), algorithms like the perceptron or Winnow.

In the remainder, we consider a number of popular techniques for encoding and decoding both discrete data, and data defined on a Euclidean space. We develop an analytic framework that unifies analysis of many of these techniques and readily leads to simple sufficient conditions under which various HD information processing algorithms will succeed.

3 Encoding and Decoding Discrete Data

A central object in HD computing is the mapping from inputs to their high-dimensional representations. The design of this mapping, typically referred to as "encoding" in the literature on HD computing, has been the subject of considerable attention, and there is a wide range of possible encoding methods targeting different types of data. Some of these have been introduced in the HD computing literature and studied in isolation [Plate, 2003; Gallant and Okaywe, 2013; Kleyko et al., 2018]. We here present a novel unifying framework in which to study these mappings and to characterize their key properties in a non-asymptotic setting. We first discuss the encoding and decoding of sets in some detail. Many HD encoding procedures for more complex data types such as sequences essentially amount to transforming the data into a set and then applying the standard set-encoding method.

3.1 Finite Sets

Let A = {ai}mi=1 be some finite alphabet of m symbols. Symbols a ∈ A are mapped to H under an encoding function ϕ : A → H. Our goal in this section is to consider the encoding of sets S whose elements are drawn from A. The HD representation of S is constructed by superimposing the embeddings of the constituent elements using the bundling operator ⊕ : H×H → H. The encoding of S is defined to be ϕ(S) = ⊕a∈Sϕ(a). We first focus on the intuitive setting in which ⊕ is the element-wise sum and then address other forms of bundling.

To determine if some a ∈ A is contained in S, we check if the dot product ⟨ϕ(a), ϕ(S)⟩ exceeds some fixed threshold. If the codewords {ϕ(a) : a ∈ A} are orthogonal and have a constant length L, then we have ⟨ϕ(a), ϕ(S)⟩ = L2 1(a ∈ S), where 1 is the indicator function which evaluates to one if its argument is true and zero otherwise. However, when the codewords are not perfectly orthogonal, we have ⟨ϕ(a), ϕ(S)⟩ = L1(a ∈ S) +∆, where ∆ is the "crosstalk" caused by interference between the codewords. In order to decode reliably, we must ensure the contribution of the cross-talk is small and bounded. We formalize this using the notion of incoherence popularized in the sparse coding literature. We define incoherence formally as [Donoho et al., 2005]:

Definition 1. Incoherence. For µ ≥ 0, we say ϕ : A→H is µ-incoherent if for all distinct a, a′ ∈ A, we have

When d ≥ m, it is possible to have codewords that are mutually orthogonal, whereupon µ = 0, however we are generally interested in results that do not require d ≥ m.

The cross-talk noise can be bounded in terms of the incoherence of ϕ, which in turn leads to a simple threshold rule for decoding:

Theorem 1. Let L = mina∈A ∥ϕ(a)∥ and let the bundling operator be the element wise sum. To decode whether an element a lies in set S, we use the rule

This gives perfect decoding for sets of size ≤ s if ϕ is 1/(2s)- incoherent.

We now turn to practical methods for generating incoherent codebooks.

3.2 RandomCodebooks

In practice, each ϕ(a) is usually generated by sampling from some distribution over H or a subset of H [Kanerva, 2009; Kleyko et al., 2018; Rahimi et al., 2018]. We typically require that this distribution is factorized so that coordinates of ϕ(a) are i.i.d.. Intuitively, the incoherence condition stipulated in Theorem 1 will hold if dot products between two different codewords are concentrated around zero. Furthermore, we would like it to be the case that this concentration occurs quickly as the encoding dimension is increased. It turns out that a fairly broad family of simple distributions, known as the sub-Gaussians, satisfies these properties.

We can show that codebooks sampled from any subGaussian distribution are incoherent with high-probability, provided one chooses d to be large enough:

Theorem 2. Let ϕ be σ-sub-Gaussian. Then, for µ > 0,

Throughout our work, we consider three running examples of codeword distributions (although our approach is generic to any sub-Gaussian distribution). In the first, we consider codewords sampled from the uniform distribution over the ddimensional unit-cube. In the second, codewords are sampled from the d-dimensional standard-Gaussian distribution. In either case, one can show that, with high-probability µ = O(√(lnm)/d), meaning that (by invoking Theorem 1) the encoding dimension scales quadratically with the number of elements in the set, but only logarithmically in the alphabet size and probability of error. However, we show that the dependence on s can be reduced to linear in exchange for a slightly weaker bound that just guarantees that any arbitrary set will be correctly decoded with high-probability. Finally, we also consider sparse binary codewords, which have an interesting connection to the Bloom filter [Bloom, 1970], which is a popular approximate data structure for representing sets.

3.3 Encoding Structures

We are often interested in representing more complex data types, such as objects with multiple attributes or "features." In general, we suppose that we observe a set of features F whose values are assumed to lie in some set A. Let ψ : F → H be an embedding of features, and ϕ : A → H be an embedding of values. We associate a feature with its value through use of the binding operator ⊗ : H × H → H that creates an embedding for a (feature,value) pair. For a feature f ∈ F taking on a value a ∈ A, its embedding is constructed as ψ(f) ⊗ ϕ(a). A data point x = {(fi ∈ F, xi ∈ A)}ni=1 consists of n such pairs. For simplicity, we assume each x possesses all attributes, although our analysis also applies to the case that x possesses only some subset of attributes. The entire embedding for x is constructed as [Plate, 2003]:

As with sets we would typically like ϕ(x) to be decodable in the sense that we can recover the value associated with a particular feature, and comparable in the sense that ⟨ϕ(x), ϕ(x′ )⟩ is reflective of a reasonable notion of similarity between x and x′ . It turns out that these desiderata are again related to a notion of incoherence in the embeddings. We omit a technical discussion here, since the gist is similar to the discussion of sets above, but full detail is available in [Thomas et al., 2021].

3.4 Robustness to Noise

We conclude our treatment of encoding discrete data by exploring the noise robustness properties of the encoding methods discussed above using the formalism of incoherence. We consider some unspecified noise process which corrupts the encoding of a set S ⊂ A of size at most s according to ˜ ϕ(S) = ϕ(S) +∆S. We say ∆S is ρ-bounded if:

We are interested in understanding the conditions under which we can still decode reliably.

Theorem 3. Suppose S has size ≤ s and ∆S is ρ-bounded. We can correctly decode S using the thresholding rule from Theorem 1 if:

where L = mina∈A ∥ϕ(a)∥2.

We specialize this analysis to several different practical types of HD architecture and address both passive noise, and adversarial noise in which ∆S might be chosen maliciously, with knowledge of the codebook, so as to deliberately cause a decoding error.

4 Encoding Euclidean Data and Learning

We additionally address encoding of data defined over a Euclidean space X ⊂ Rm. In general, one typically here desires that the HD encoding preserve a notion of distance on the original data, which we formalize as follows:

Definition 2. Distance-Preserving Embedding: Let δX be a distance function on X ⊂ Rn and δH be a distance function on H. We say ϕ preserves δX under δH if, there exist functions α, β : Z+ → R such that β(d)/α(d) → 0 as d → ∞, and:

We typically wish the distance function δH on H to be simple to compute. In practice, it is often taken to be the Euclidean, Hamming, or angular distance. We show that this definition is satisfied by several popular forms of encoding in HDC and provide closed form expressions for α(d), β(d), which allows practitioners to determine an encoding dimension (d) sufficient to preserve a distance with desired fidelity.

Distance preservation also has important implications for learning on HD data representations. We show that distance preservation is a sufficient condition to establish preservation of neighborhood/cluster structure, robustness to various forms of noise, and in some cases, preservation of linear separability. The latter point is important because the learning algorithms used in HDC are predominantly linear, and thus, at a minimum, encoding should preserve linear separability to the extent it exists in the data. We additionally show that, under a particular type of encoding method, linear separators on the HD version of the data are sparse. That is, they depend only on a small number coordinates in the representation. Our analysis links properties of the data-for instance a notion of margin or separability between classes/clusters-with the choice of encoding dimension, which is an important practical consideration. Moreover, we examine how certain types of encoding can actually increase the power of linear separators on the HD version of the data. That is: linear decision boundaries learned on the HD data can sometimes capture nonlinear decision boundaries on the original data-much like kernel methods frommachine learning and statistics. Indeed, many of the encoding techniques used in HD computing can be seen as approximate feature maps for different types of kernel function on the original data. We discuss these connections in greater detail in our main paper.

5 Conclusion and Discussion

A key question addressed here and by several pieces of prior work is to bound the magnitude of crosstalk noise in terms of the encoding dimension (d), and properties of the data, like the number of items to encode (s), and the alphabet size (m). Prior analysis [Plate, 2003; Gallant and Okaywe, 2013; Kleyko et al., 2018; Frady et al., 2018] recovers the same asymptotic relationship as we do, but either relies on specific assumptions about the method used to generate the codewords, or relies on asymptotic approximations. Our approach based on sub-Gaussianity and incoherence formalizes this analysis in the non-asymptotic setting.

In summary, our formalism using the notion of incoherence allows us to decouple the analysis of encoding, decoding and noise-robustness from any particular method for generating codewords and readily yields rigorous bounds in the nonasymptotic setting. Our approach unifies a large swath of HD computing under a single analytic framework, and enables us to offer general conditions under which thresholding based decoding schemes and simple learning methods will succeed.

Acknowledgements

This work was supported in part by CRISP, one of six centers in JUMP, an SRC program sponsored by DARPA, in part by an SRC-Global Research Collaboration grant, GRC TASK 3021.001, GRC TASK 2942.001, DARPA-PA-1903-03 Agreement HR00112090036, and also NSF grants 1527034, 1730158, 1826967, 2100237, 2112167, 2052809, 2003279, 1830399, 1911095, 2028040, and 1911095.