Understanding Hyperdimensional Computing for Parallel Single-Pass Learning
Authors: Tao Yu
Yichi Zhang
Zhiru Zhang
Christopher De Sa
Venue: NeurIPS 2022 Accept (2022)
Keywords: hyperdimensional computing
vector symbolic architecture

Abstract: Hyperdimensional computing (HDC) is an emerging learning paradigm that computes with high dimensional binary vectors. There is an active line of research on HDC in the community of emerging hardware because of its energy efficiency and ultra-low latency---but HDC suffers from low model accuracy, with little theoretical understanding of what limits its performance. We propose a new theoretical analysis of the limits of HDC via a consideration of what similarity matrices can be ``expressed'' by binary vectors, and we show how the limits of HDC can be approached using random Fourier features (RFF). We extend our analysis to the more general class of vector symbolic architectures (VSA), which compute with high-dimensional vectors (hypervectors) that are not necessarily binary. We propose a new class of VSAs, finite group VSAs, which surpass the limits of HDC. Using representation theory, we characterize which similarity matrices can be ``expressed'' by finite group VSA hypervectors, and we show how these VSAs can be constructed. Experimental results show that our RFF method and group VSA can both outperform the state-of-the-art HDC model by up to 7.6\% while maintaining hardware efficiency. This work aims to inspire a future interest on HDC in the ML community and connect to the hardware community.

Understanding Hyperdimensional Computing for Parallel Single-Pass Learning
Tao Yu'
Yichi Zhang" Cornell University y22499@cornell.edi
Coreell University tyu@cs. www.eolooeloooooooe
Zhiru Zhang Cornell University zhiruz0cornell. edu
Christopher De Sa
Cornell University cdesa@cs. cornell... edu
Abstract
Hyperdimensional computing (HDC) is emerging learning paradigm that com- putes with high dimensional binary vectors. There an active line research HDC in the community of emerging hardware because of its energy efficiency and ultra-low latency-but HDC suffers from low model accuracy, with little theoretical understanding of what limits its performance. We propose a new theo- retical analysis of the limits of HDC via a consideration of what similarity matrices can be "expressed" by binary vectors, and show how the limits of HDC can be approached using random Fourier features (RFF). We extend our analysis to the more general class of vector symbolic architectures (VSA), which compute with high-dimensional vectors (hypervectors) that are not necessarily binary. We propose new class of VSAs, finite group VSAs, which surpass the limits of HDC. Using representation theory, we characterize which similarity matrices can "expressed" by finite group VSA hypervectors, and we show how these VSAs can be constructed. Experimental results show that our RFF method and group VSA can both outperform the state-of-the-art HDC model by up to 7.6% while maintaining hardware efficiency. This work aims inspire future interest HDC in the ML community and connect to the hardware community.
1 Introduction
Hyperdimensional computing (HDC) is emerging learning paradigm. Unlike conventional cogni- tive modeling that computes with real numbers, it computes with high dimensional binary vectors, referred as binary hypervectors,, the dimension of which is usually least in the thousands. HDC brain- irain-inspired as high dimensional representations have two fundamental properties similar to human brains: they are (1) distributed and highly parallel; and (2) robust to noise and tolerant to component failure Kanerva 2009). On the other hand, the massive parallelism and simple arithmetic project HDC into the scope of energy-efficient and ultra-low-latee -ltency computing, especially with the rise of emerging hardware [Imani et al. 2021] 2020 Gupta et al.] [2020] Salamat et al. 2019]. As result, HDC has recently attracted considerable attention from edge applications, e.g., robotics, DNA pattern matching, and health diagnosis, as well as data center applications such as recommendation
systems [Mitrokhin al. 2019 Neubert al. 2019 Neubert and Schubert 202T
Kim et 2020
Burrello et al. 2019 Guo et al. 2021
'Equal Contribution.
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

The practical deployment of HDC is undermined by its low model accuracy compared to other alternatives, e.g.. neural networks (NN). The otate-of-the-art HDC model on MNIST has an accuracy of 89% [Chuang et al. 2020 A two-layer NN, however, can easily achieve 95% [ecun et al. 1998
There are two main approaches in the literature improving HDC. One approach is to increase the hypervector dimension, staying within the classic HDC paradigm and just making the binary vectors longer [Neubert al. 2019 Schlegel al. 2021 An alternative
increase the complexity of
each element in a hypervector, c.g., to flotting point or complex numbers (unit circle in the complex
plane) [Plate| 1995 Gallant and Okaywe, 2013 Gayler 1998 Plate 1994]: this moves the system
into the more general realm of vector symbolic architecture (VSA) Schlegel et al.) 202T), which uses high-dimensional vectors with elements that are not necessarily binary (unlike binary HDC). However, these remedies are not based on any theoretical analysis of the limits of HDC, and as result there a lack of more-than-een -rrethaa-emmiiiall understanding of when and how they should be deployed.
In this work, we introduce a new notion of expressivity for any VSA using similarity matrices. Given a set of hypervectors ....... Un in VSA, each entry My; in the similarity matrix M is defined as the similarity between a pair of hypervectors inner product function. Informally, we propose that VSA is more expressive when can express (i.e. represent with some set of vectors) a wider class of similarity matrices. Importantly, which M a VSA can express independent of the vector dimension D: this new notion distinguishes between longer-vector and more-complex-verr -vector approaches.
and uy; the similarity is typically measured by an
We show that HDC, with binary hypervectors even in any dimension, cannot express as many similarity matrices that a VSA with more complex hypervectors can. Even worse, the current method of initializing the hypervectors in an HDC system further reduces the expressible set, which impedes the success of HDC. This notion of expressivity is closely related to learning ability. We exhibit simple task where current HDC (of any D) is incapable of learning a Bayes optimal classifier, while any other VSA system that can express a particular similarity matrix M (which HDC cannot express) can learn it through the same procedure.
Based on our analysis, we investigate how we can improve HDC through the lens of similarity matrices. We first propose to improve the initialization of binary hypervectors by employing random Fourier features (RFFs) [Rahimi and Recht [007]. This method is different from existing approaches that increase the dimension complexity of hypervectors. We show that this better initialization via expressing a similarity matrix can already surpass state-of-the-ar HDC accuracy on MNIST by 6.4%. We then propose and formally define group VSA, extended version of HDC where elements in hypervectors are more complex than binary but less than floating-point Group VSA can further improve the RFF-initialized HDC by 1.2% on MNIST.
Our contributions are as follows:
We provide a theoretical analysis of the limitations of an HDC system with binary hypervectors.
We approach the expressivity limit of HDC systems with random Fourier features and empirically evaluate the improvements on standard benchmarks.
We propose group VSA, which generalizes HDC with more complex elements, expanding the set of expressible similarity matrices while maintaining efficiency.
We evaluate the performance of group VSA on both conventional HDC tasks and image tasks, and study its efficiency implications by analyzing the circuit depths.
2 Related Work
The term HDC was first introduced by Kanerva 2009 It is also referred to VSA in some literature [Schlegel et al. 202T]. a line of work that does symbolic computing. Binary HDC can be traced back to Binary Spatter Code (BSC) [Kanevaa 1994 Kanerva et al. 1997
Model capacity improvement. There are two main VSA formats other than binary HDC: using
floating-pon -piin real vectors [Plate| 1995 Gallant and Okaywe, 2013 Gayler 1998 Gosmann and
Eliasmith] 2019) or complex vectors [Plate| 1994]. Typically their model capacities are higher since their individual vector components are more complex. Another way of increasing the model capacity increasing the vector length [Neubert et al. 2019, (Schleell et al., 202T Chuang et al.) 2020 Frady et al.) 2018 However, it remains unknown when and how we should apply these methods, and

---

whether they are sufficient to solve a task. Our approach is different as our proposed methods are based on the theoretical analysis of, and are designed to bypass, the limits of binary HDC.
Hardware implication. HDC inspires a novel hardware architecture that requires associative memory [Hopfilld 1982] where long vectors can be stored and addressed efficiently. It is therefore popularized
recently in the emerging in-eemory computing community [Imani et al. 2020 Gupta et al. 2020].
In the meantime, the simplicity of HDC arithmetic and the massive parallelism make HDC suitable for tasks that require high energy efficiency and low latency. It has been demonstrated successful on
commercial hardware as well [Imani al. 2021 Salamat al., 2019 Basaklar et al. [202T] In this
work, we provide an analysis on the circuit depths of HDC and our proposed group VSA.
Theory. Understanding HDC from theoretical perspective is currently limited. Thomas al.) 2020 Frady et al. 2018) presented some theoretical foundations of HDC, introducing the benefit of high-dimensional vectors, hypervector encoding, and the connection between HDC and kernel approximation. Our work instead presents the limits of HDC and how we can bypass it. |Frady et al.) [02I]] propose to generalize VSA/HDC to function space. Our work is different since our proposed group VSA, generalization of HDC, is still discrete and preserves the hardware efficiency.
3 Background on HDC
In this section we introduce basics of HDC: hypervectors, arithmetic, and the learning paradigm. We then present a classical approach of HDC on the popular MNIST database. more comprehensive introduction is in Ge and Parhi 2020).
HD Representations. In HDC, we compute with binary hypervectors high-dimensional space re- ferred to as hyperspace. Given random hypervector v in 10, 000 dimensional space {-1, 1] 10,000 is well known from the "curse" of dimensionality that most vectors this hyperspace are nearly orthogonal to e (Kanerval 2009]. We call such hypervectors unrelated. The "curse" provides two intriguing properties for cognitive tasks: (1) independent random hypervectors will be unrelated and so can naturally represent objects that are semantically separate, e.g. letters of the alphabet; (2) two hypervectors u and that have a high-enough inner-product similarity can be classified as being related (i.e. somehow dependent) with high probability. Classical HDC therefore represents data using binary hypervectors randomly drawn from hyperspace. HDC computes with hypervectors using a fixed set of primitive operations: similarity, binding, bundling, and permutation.
Similarity. A similarity function S(u, v) measures how close two hypervectors u, u E (-1, are.
is typically defined as an inner product function (Frady et al. 2021 S(u, D i=1 2 this
is an affine function of the hamming distance for binary hypervectors (Kanerva 2009
Binding X The binding operation combines two hypervectors u, u into a new hypervector in the same space that represents them as pair. For binary +11,+ binding is equivalent to coordinate- and (u v): = u,,; for all i (1,.... D}. Binding preserves similarity, in the sense that S(u @ w, u 6 w) = S(u, u) for any hypervectors v, and w; also, if u highly similar to v and x highly similar to y. then u 69 x will be highly similar to v ( y (although usually less than either constituent pair). Binding is implemented on hardware an XOR.
wise multiplication, i.e. (u & v) E [[11,+1]
Bundling D Bundling represents an unordered collection of hypervectors. The bundling operation takes in a set of hypervectors and yields hypervector that is maximally similar to all of them: it acts as an aggregation of set of hypervectors. Bundling ....... Um E f-1, +1} yields (4 k=1 U*), =
sgn >>== (wx),) for all E (1...., D). This takes a majority vote each coordinate of the vector; ties are broken at random. HDC typically leverages bundling to learn a class representative.
Permutation I[. The permutation operation is shuffling of the elements in hypervector. It can be represented as multiplication of a permutation matrix 11. A random permutation on hypervector yields another hypervector that is unrelated to it. Note that permutation is invertible, meaning that -1-; v. It is thus useful for encoding order and position information. In hardware, permutation usually appears as shifting since its implementation efficient.
3.1 MNIST Case Study
We outline how to use the classic HDC approach the MNIST digit recognition task for illustration.
3

---

Encoding. First, 256 basis hypervectors fro, 0i..... U255 } are independently drawn at random from hyperspace [-1,+13 each hypervector v; represents a pixel intensity i. Second, we bind all 784 pixels in an MNIST image by their corresponding hypervectors. Since the binding operation commutative by definition, but pixels in an image have meaningful relative positions, each pixel hypervector is shifted before joining the encoding to preserve that position information. If the input pixel intensities are po: Pt..... P783, then its encoded hypervector is Upo @ (1Ipp)) @ 8..-6 (117883pp7s) Up7ss) where IP denotes shifting hypervector; j times.
Learning. Encoding yields a set of training hypervectors T {4,, 111,422..,,,...... }.
To learn, we bundle all the hypervectors that from the same digit. Concretely, class centroid s, is computed by 86
+ #/y 4. Each training image is used only once, making this process single-pass learning.
Inference. At the inference time, a given test image is encoded through the same procedure. The model outputs the class with the highest similarity S(treu Sc).
Similarity Matrices and the Limits of HDC
Traditionally the expressivity of HDC setups is identified with the dimension of the hypervectors D. This notion is unhelpful for probing the fundamental limitations of HDC, which do not depend on D. In this section, we define a new notion of expressivity, which reveals the limits of HDC.
Definition 1. An HDC (or VSA) system can express a similarity matrix M E Rax" ffr any > O. there exists D E N and D D-dimensional hypervectors v1, U2..... Un in the HDC/VSA such that [M,- - S(u, U,)l I E where S denotes the similarity function of the HDC/VSA.
Informally, this means that the HDC/VSA can approximate M arbitrarily well. Limitations on M we can express correspond limitations on the similarity relation we can represent on data: if have some dataset and know how similar each pair of examples should be, whether or not we can represent the similarity accurately with an HDC embedding depends on whether HDC can express the corresponding M. Surprisingly, there are some matrices that an HDC system can never express.
Lemma 4.1. Binary HDC can not express the matrix M 4.1
Is
1 1 13x3. 2
Our notion of expressivity corresponds to learning ability, we give an example task for which whether VSA/HDC approach learn the Bayes-optimal classifier depends on whether it can express Meemmo Consider a supervised learning task with input set = (0. 1, 2}, output label set y = X, and source distribution (ar,, y) :===)):1) (1/9 2p) if x y else (1/9 p) for some small positive number We say that a VSA can learn this task if there exists a D-dimensional encoding of X' in that VSA such that, when the bundling method in Section B. used training of size N drawn from P. the resulting classifier is the Bayes optimal classifier with arbitrarily high probability as N increases.
Statement 4.1. Binary HDC cannot learn this task. Any VSA (formalized later in Desinition 2 that can express M1 can learn this task.
Details on Statement 4.1 are in appendix. This learning task shows that only increasing the dimen- sionality of hypervectors cannot help learn the correct predictions unable to express a certain matrix. This implies that our notion of expressivity captures HDC limitations in way that relates to learning.
Limitations due to initialization. So far in this section we have described limitations that are inherent to using binary representations in a VSA. Classical HDC methods are often limited in an additional way: rather than considering arbitrary binary hypervectors, they use hypervectors that are sampled independently at random. In such system, any hypervector used for an embedding (used to represent an entity) is constructed either by (1) independently sampling a binary hypervector where each entry has some probability of being 1, or (2) permuting and/or binding some pre-existing hypervectors. Examples of this setup can be found in Burrello et al. [2019], [mith and Stanford [1990), Imani et al. [2019b). Surprisingly, we show that this approach further restricts the set of similarity matrices that can be expressed in expectation.
Lemma 4.2. Let u1, u2,..., uk be binary vectors sampled coordinate-wise independently random, where each coordinate of u; has the same probability pe of being 1. Lei Vo, vn, and V2 be vectors that result from some composition of binding and permutation operations acting on ; and let
uk

---

M E R 3 be their similarity matrix, such that M.j = S(v,, vz). Then
M
y2 3
but this target matrix can be expressed by binary HDC.
5 Encoding Hypervectors via RFF
Our analysis using similarity matrices provides a strong motivation for using more principled methods construct hypervectors. We argue that, if there is some similarity matrix M we want to achieve, we should directly instantiate hypervectors to match it in expectation.
A natural way to represent desired similar- ity matrix M E R=** is to project onto the set of representable matrices of binary vec- tors, which would correspond to a distribu- tion could sample from. Unfortunately, this approach is intractable as it would re- quire solving linear programming problem of size exponential in n. Instead, to approach the expressivity limits of binary HDC, propose the following approach, given in Algorithm First, we sample d independent multivariate Gaussians over I"; Our HDC vectors of length d are then given by the signs of these Gaussians. The following lemma tells us how to make this produce desired similarity matrix M.
Algorithm Construct correlated hypervectors input: similarity matrix M R"*", dimension d let E sin( M (elementwise)
let UAU = Σ (symmetric eigendecomposition)
sample X E R iid unit Gaussians
return sgn sgn(U (UA)22 2 x) [clementwise]
Lemma 5.1. Suppose X, are jointly Gaussian zero-mean unit-variance random variables, then E[sgn(X) (X) sgm (Y) = 2 aresin (E[XY]).
From this lemma, it immediately follows that if the elementwise sin of M is positive semi-defiitt, then Algorithm| [ produces hypervectors that, in expectation, exactly achieve M; otherwise, some approximation to M is produced. It also immediately follows that Algorithm can achieve more similarity matrices than the classical procedure of Lemma 4.2 while that lemma shows that the similarity matrix } T 3xx3 cannot be achieved in expectation by classical HDC initialization, Algorithm can achieve as sin( )3 = 2 =1 and I 13x3 is positive semidefinite.
Algorithm gives us more freedom to achieve a wider range of similarity matrices; however, it does not tell us which similarity matrix M choose for a given task and whether sin( / M) is positive
semi-definite or not. In this paper, we use the well-known RBF kernel (Vert et al. [004] to choose the similarity matrix between entities, but any similarity matrix appropriate for task is applicable.
6 Group VSA
So far we have shown how replacing existing initialization methods can approach the limits of binary HDC. However, as Lemma 4.1 shows, binary HDC itself has inherent limits. Other known VSAs, such as the unit cycle VSA [Plate] 1994]-in which the elements are complex numbers of absolute value c-can surpass these limits. However, this comes with the problem of continuous space-requirinn both approximation and significant hardware complexity overhead compared to binary HDC. In this section, we propose new class of VSA. finite group VSA, which effectively "interpolates" between them so as to bypass the rimilaarty-represennttton limits of binary HDC without the need for continuous space.
We start by defining a VSA, and then propose to use group structures for the elements of hypervectors different approach to improve the expressivity of VSA. Binary HDC can be considered special case of our construction corresponding to the 2-element group.
Definition 2. A group VSA is tuple (G, p1 @. S, @), where G is some measurable set of symbols, 8 : G x G > G is the binding operator, S G G + R a symmetric similarity operator, and : Ghe G is the bundling operator (which maps finite sequence of symbols symbol). A VSA must have the following properties:
Binding. (G,8) is group, binding is associative over G and has inverse and identity elements.
5

---

Similarity to self.
= all Z G.
Similarity preserved by binding. 8ig8a,92 y) = ( S(z. y) for all g, g, G. Similarity extensible to an inner product. There exists (mite-dimensional Hilbert space V over R and an embedding 1/= G - V such that S(r, v) = (a)()), (g)) for all x, y E G. Equivalently, Li=1 E== C2C,S m2)) 2 0 for any 21,...., Fn E G and scalars c,...... Cn E R.
Random vectors dissimilar to any other vector. Bg-Uniformm()) (g.g x) = 0 for any G.
Bundling. Bundling of ; Im E G returns O I; arg maXgeG Di=1 S(g, 2hi) or one of the maxima in case of a tie.
To compute using VSA of dimension D, we use hypervectors in GD, extend binding and bundling to act elementwise on these hypervectors, and extend similarity to compute the average similarity
over the dimensions as S(221.... ................................ [[ [B1...... Upl) = 1 El=
D i= S(r.. W1). It is easy to see that VSA where G= (- [-1,1]1, 1). @ is multiplication, and S(x, y) = zy. binary HDC is equivalent
Similarly, unit-cycle VSA (i.e., FHRR) has G = {2 C |2| =). @ as complex multiplication, and ( y) = Re(x"y) Most other schemes called "VSAs" in literature fall under our definition, e.g., Gayler 1998), with few exceptions (Plate 1993] that violate the group requirement. In order to run efficiently on hardware, we add the following restriction.
Definition 3. A finite group VSA is VSA where G is finite. That is, (G,8) is a finite group.
On hardware, finite G allows the VSA elements to he represented exactly and lets the VSA operations be computed exactly. The hardware cost will depend on the size of G. In many cases, we would like binding to preserve similarity in a stronger sense than that guaranteed by Definition [ It is often desirable that the similarity after binding is the product of the similarities before binding, i.e.,
S(x1 @ 22; 1/1 & y2) = S(x1, y1) S(22, (x2,))));
this would make @ behave like a tensor product space with inner product given by S. This property is particularly important, usually when an object consists of multiple features, we will bind these features so as to derive a representative vector for the object, this property ensures that two objects with multiple pairs of similar features to have similar representative vectors.
Of course this equation is not guaranteed to hold for elements of G in general (e.g., when Ii @ x2 = yn @ y2); however, most VSAs can approximate this behavior by adding an extra randomization step. Definition 4. Let A denote the uniform distribution over automorphisms of (G, S) Then we say that VSA has the product property if for any 1 32, y y2 G, AS @ a(x2)) y11 @ a(y=))] = Ea ((((((((( @ x2, (11) & y2)] = S(1 vn) S(22, v2)-
It is easy to see that this holds for binary HDC, as the identity map is the only automorphism of 2 2 and (T) holds for binary HDC: this also holds for the unit cycle VSA, where the only automorphisms are the identity (z + 2) and the complex conjugate automorphism (z + 2*). Rather than using this transformation directly, if one exists we can ensure this "product property" holds by initializing our hypervectors appropriately: if we sample hypervectors (x1,2) at random with independent entries and independently of (122, 3/2) and both distributions are invariant under automorphisms, then B[S ( @ 22, V1 @ y2)] ([S( 91)] E[S(222))2)
6.1 Constructing VSA from finite group
At first glance, the definition of a group VSA may seem open-ended, offering little guidance as to what the limitations of finite group VSAs may be and how they can be constructed. Surprisingly, we can fully characterize the finite group VSAs through representation theory. We start by introducing definitions specialized to mnite-dimensional complex representations, before stating the full theorem.
Definition (James et al. 2001 Fulton and Harris [2013). A representation of a group G over C" is a group homomorphism p from G to Cux such that p(gh) (()) for all g, h E G.
The character of a representation p is the function x : G + given by x(g) = Tr(p(g)). The representation (and corresponding character) is said to be irreducible if no proper subspace of C" is preserved by the group action. The trivial representation, had by all groups, is p + CIX1 with p(g) 1 and x(g)= 1.
is a standard result that each finite group possesses a finite number of irreducible characters equal to the number of conjugacy classes of the group (Serre 1977 Fulton and Harris 2013

---

Theorem 6.1. Let (G,8) be finite group, and let X denote the set of its non-trivial irreducible characters. Let X-222 be some function that assigns a non-negative weight to each of the characters. Then, if we set S as S(g, h)= Exex o(x) R
where the inverse and unit are those of the group, and define bundling D as given in (2. then (G, &, ②) is a finite group VSA. Any finite group VSA can be constructed in this way. If in this construction a is supported only one character X. i.e. S(g, h) = Re(x(g- & (1),, then the VSA will have the product property.
2xcx alx)xx(1)
This construction makes it seem as though finite-group VSAs with the product property may be a restricted subset, which could be less expressive. The following result shows that this is not the case.
Statement 6.1. Let M be a similarity matrix expressible by a finiee group VSA. Then there exists a finite group VSA that has the product property and can also express M.
6.2 Cyclic Group VSA
Most of our work with group VSAs in this paper will use the cyclic group G = Σ/nž =
{0, 1,.... 1}. Definition indicates, we first provide an embedding &i G + V
miite-dimensional Hilbert space V over R. Let (zx)= = (cos(2xx/n) sin sin(2nz/n))
Definition 6. The standard cyclic group VSA is given by:
The symbol set = 2/nZ = {0, 1, .... , n--13 with addition modulo n as binding operation X. Similarity is defined as S(z, v) = (1b()) vb1) cos(2 (x y)/n).
This cyclic group VSA is in some sense a "subset" of the unit cycle VSA, and as n goes to infinity, it approximates the the unit cycle VSA arbitrarily well [Plate] 1994), serving as an interpolation between the binary HDC and the unit cycle VSA. As straightforward consequence, any M that can be expressed by this VSA can also be expressed by the unit cycle VSA. To compute with this VSA, we follow the procedure in Section use hypervectors in GO, and extend similarity, binding and bundling operations accordingly. Similar to the HDC case, we utilize random Fourier features for a better basis hypervectors initialization with minor modifications of Algorithm T we replace the sgn function in the last step with the (nth) quantile function of a Gaussian so as to map into G.
Note that as Theorem 6.1 shows, this setup is not the only VSA over the cyclic group. Indeed, for any distribution a over (1,.... n 1}. the similarity function S(x: y) = Ei= (xk) cos (2m(==))k would yield a finite group VSA. We focus on the VSA of Definition
6 because satisfies the product property, and all other VSAs on G that do so are either isomorphic to it or isomorphic to the same construction with smaller n.
6.3 Non-Abelian Finite Group VSAs
Our analysis of cyclic group VSAs from the previous section extends naturally to cover all finite Abelian groups (i.e. groups in which @ is commutative), since is a classic result that every finite Abelian group factors the direct product of cyclic groups. It is natural to ask: what about non- Abelian groups? Because they simplify both representation and computation, it would be convenient if we could restrict our attention to Abelian groups only. Unfortunately, the following two statements together show that non-Abelian groups can be strictly more expressive than Abelian groups
Any similarity matrix M that can be expressed by a finite Abelian group VSA can be expressed by the unit-cycle VSA (G = {a E C' | |z| = 1}. x @ y = zy. S(x, y) = Re(x"y))
Statement 6.2.
Statement 6.3. There exists similarity matrix M that can be expressed by a VSA over the (non- Abelian) binary icosahedral group, but not by the unit-cycle VSA (i.e., FHRR).
Statement 6.2 follows from the standard representation- thhooreti result that all irreducible repre- sentations of a finite Abelian group are one- one-dimensional, while Statement 6.3 proved by direct construction. While these results do show that, non-Abelian finite group VSAs are "more powerful" than Abelian finite group VSAs, the additional complexity needed to unlock this power seems not worthwhile for our applications, where unit-cycle VSA already performs well so, in our experiments we focus solely on the cyclic group. We leave exploration of non- Abelian VSAs to future work.
7

---

Table 1: Comparison on test accuracy proposed methods to SOTA HDC Imani et al.
2019a|
dynamic HDC" [Chuang al., 2020) and 1-bit RFF perceptron. Dimension of hypervectors is 10,000.
1-Epo: 1-Epoch, 10-Epo: 10- 10-hp.
Dataset
ISOLET
UCIHAR
MNIST
Mishion-MNISS
Acc(%)
I-Epo
10-Epo
1-Epo
10-Epo
1-Epo
10-Epo
1-Epo
10-Epo
Percep.
82.8
90.1
69.3
91.4
94.3
94.3
79.5
79.5
HDC
85.6
91.5
87.3
95.7
NA
89.0
NA
NA
RFF HDC
90.6
94.4
93.8
95.7
95.4
95.4
83.4
84.0
RFF G(2")-VSA
93.1
94,4
95.1
95.6
96.3
95.7
85.4
86.7
RFF G(21)-VSA
94.4
96.0
95.5
96.6
96.5
96.6
87.4
86.5
7 Learning via SGD Instead of Bundling
Prior works train an HDC model via bundling hypervectors in the same class Tr = (t.[label(tt)) c}. This is based on the fundamental assumption about bundling that the class representative is similar to each 4, We find that it not always true, depending on the number of vectors being bundled.
Suppose a set To has 2k + (avoids a tie) unrelated hypervectors, we can theoretically calculate the expected angle between 8, and a randomly selected hypervector 4;: 02R+1 = arccos ((2) /22)
This indicates that the class vector learned from bundling will be nearly orthogonal to each hypervector in the class and no longer be its representative as we increase k.
As an alternative, we propose to leverage stochastic gradient decent (SGD) to learn linear classifier (same precision). Take binary HDC as an example, classifier a binarized matrix multiplication at inference time, i.e., O == X sgn(W), where X is the binary hypervector and W is the weight matrix. During the back propagation, we use the straight-through estimator (Hubara et al. 2016) to approximate the gradient of the sign function: @ sgn (W)/WW' := 1 [W| <
else O.
The inference cost of an HDC model remains the same the bundling paradigm since they are both binary. The model is still trained for one or few epochs so the SGD approach incurs minor training overhead. We defer the SGD learning process of group VSAs to Appendix.
8 Experiments
Datasets. We evaluate the performance of proposed methods on two conventional HDC datasets, ISOLET [Dua and Graff 2017) and UCIHAR (Anguita et al., 2012]. We also evaluate our method on MNIST and Fashion-MNIST Xiao al.) 2017]. which are more challenging for HDC. ISOLET is speech recognition dataset where each sample is an audio signal with 617 features. Each feature is in the range of [-1.1] 1]. The dataset has 7719 samples in total. The goal is predicting which late was spoken. UCIHAR is a human activity recognition database, each sample of which contains 561 features collected from smartphone sensors. The features are also in the range of [-1, The database has 10299 samples. The task is predicting which type activity a human was performing.
Setups. For ISOLET and UCIHAR, we quantize the features to 8 bits before encoding. We initialize a 10.00o-dimensional basis hypervector for each -.. 255} feature value, then encode raw inputs learning rate of 0.01 and train classifiers for 10 epochs. We compare RFF-HDC and group VSA of order 2 and 24 with SOTA HDC Imani et al. 2019a Chuang et al. 2020 that propose iteratively updating the class vectors through misclassified examples. We also compare HDC to a perceptron [Rosenblatti 1958 where binary RFFs generated from raw data. We train Intel Xeon CPUs.
as described in Section 6 During the training stage,
inputs are
Results. 1- and 10-epoch test accuracies are Table which yield three key observations:
RFF HDC already improves non-trivially over the baseline SOTA HDC. With basis hypervec- tors initialized from the similarity matrix constructed from pixel similarities, method improves
The caleulation appendix.
Hermandez--aan Cane et al. 2021 seem to have a better result on MNIST in Figure 7, but no concrete numbers reported.

---

Table 2: Analysis of circuit-depth complexity of binary HDC and 1-bit RFF pereeptron.
ps
Fex Arrunry
Circult- Deghhhh Corn pipplliityy
Test Accuracy
84
Method
CDC
Percep. 91 + 96 log, log, D. (1 log,
200
HDC
log, N + +1 # 2 log, D (1 + log, D)
200
G(2")-VSA
3n log, N + 24 log, D
2
2
Group Order
Figure I: Cyclic Group VSA on MNIST. the MNIST model accuracy by 6.4% compared to the SOTA. It also for the first time enables HDC learning on Fashion-MNiST, a more challenging task, obtaining 84% final accuracy.
Group VSA improves the model accuracy further. By extending HDC to group VSA, the vector elements are in a higher complexity that it more preciscly approximate the target similarity matrix than binary hypervectors. Figure [ shows that when there are 8 or 16 elements in the group, meaning the precision of each element in the hypervector is or 4 bits, the proposed group VSA strikes a good trade-off between accuracy and complexity. It can further outperform RFF HDC by at least 1% across various datasets.
Our HDC models learned from a single pass over the data achieve high accuracy. In all the evaluated tasks, our proposed RFF HDC or the extended group VSA both achieve approximately the final accuracy in one single epoch. In some cases, e.g., Pashion-MNIST the group VSA can accuracy of HDC is significantly better than the baseline perceptrons. especially on the ISOLET and UCIHAR datasets, which has at least 8% gap. This evidence shows that HDC learning has an impressive data efficiency. This capability of single-pass learning is consistent with finding in Imani et al. 2019a
obtain better quality with one single pass. The songleppass, model
prior works Hermandez-Cam et 2021
8.1 Circuit-Depth Complexity
To quantify the potential hardware latency of HDC, we analyze its circuit-depth complexity (CDC) in T defined the length of the longest path from the input the output (measured by the number of two-input gates along the path). CDC is commonly used to analyze the complexity of Boolean functions. We further assume that operations without data dependencies are all in parallel. Let N be the feature vector length, e.g., N = 784 for an MNIST image, D be the hypervector dimension.
Binary HDC. The encoding stage binds all feature hypervectors, which can be implemented in tree structure. The depth of single binding operation (XNOR) is 1. The total depth is therefore log, N. Computing the similarity includes a binding and bit counting. We assume B-bit ripple carry adder, a chain of full adders, has a depth of 3- B (Satpathy 2016). Therefore a D-bit population count has a 3 log, D 3 log, D (1+log, D).
depth of 3 6 +
Cyclic Group VSAs. For a cyclic group VSA of order 2n, the depth of single binding is 3n as an addition over the group. Therefore, binding all features has depth of 3n log, N. For similarity computations, we precompute the similarity matrix, which consists of S(x, y), Vx, y E G in 8-bit numbers. Hence, the depth of computing the similarity for hypervectors is 3 8 log, D.
1-bit RFF perceptron. Projecting a feature vector onto selected basis requires depth of a b2- multiplier and an adder. A 32-bit Wallece tree multiplier [Wallace, 1964] has roughly a depth of 45. 32- bit ripple carry adder has a depth of 96. A cosine operation generating random fourier features requires about the same depth as 32-bit multiplier if computing with the CORDIC algorithm [Volder 1959]. Since the perceptron is 1-bit, computing the distance has the same depth as that of HDC.
As a result, binary HDC has CDC of 295 on MNIST and the cyclic group G(23) VSA has 405. The complexity of HDC is 4.4x lower than 1-bit RFF perceptron with depth of 1 1299, while CDC of the cyclic group G(23) VSA is 3.2x lower. HDC and group VSA are much faster in potential. In Figure we plot the performance and CDC of a cyclic group VSA when the order varies. Our code is available on github

---

8.2 Discussion
The performance of various HDC/VSA methods closely related to the of its expressible similarity matrices. As matter of fact, the required similarity matrix to learn (some) tasks in the paper might already be covered by (or close to in terms of Frobenius norm) the set of expressible similarity matrices of the 10k-dimensional RFF HDC. Hence, the improvement from group- VSA can be limited compared to RFF HDC. If instead considering a 1k-dimensional binary RFF HDC with a smaller set of expressible similarity matrices, group- VSA demonstrates much better accuracy improvement. For example, on MNIST, Ik-dimensional binary RFF HDC achieves 65.59% 10-epoch test accuracy on MNIST. (-SA,,,,, meanwhile, achieves 88.61%, and G(2")-VSA achieves 92.56% test accuracy.
The circuit depth serves as a preliminary analysis on the hardware complexity of HDC. While other efficient circuits, e.g.. parallel adder instead of ripple carry adder, will have lower depth and make HDC attractive further, we avoid being over-optimistic on the estimation. For a practical hardware implementation, better circuits should be applied. Besides, circuit depth only reflects the latency. In the future, an estimation on the number of operations will reflect the energy or circuit area and will further improve the analysis.
9 Conclusion
From our theoretical analysis, there is clear connection between the class of expressible similarity matrices and the expressivity of HDC/VSA. This new notion of expressivity reveals the limits of HDC that computes with binary hypervectors, and meanwhile provides hint on how we can improve it. The nontrivial improvement from group VSA and the proposed techniques on HDC across various benchmarks suggests that this notion paves new way towards the future development of HDC/VSA.
Acknowledgments and Disclosure of Funding
This work is supported in part by NSF Awards IIS-2008 102 and CCF-2007832, and by CRISP, one of six centers in JUMP, a Semiconductor Research Corporation program sponsored by DARPA. The authors would like to thank Denis Kleyko from the Redwood Center for Theoretical Neuroscience at UC Berkeley and researchers from VSAONLINE for providing valuable feedbacks on earlier versions of this paper.
References
Davide Anguita, Alessandro Ghio, Luca Oneto, Xavier Parra, and Jorge L. Reyes- Ortiz. Human activity recognition on smartphones using a multiclass hardware-friendy. support vector machine. In José Bravo, Ramón Hervás, and Marcela Rodríguez, editors, Ambient Assisted Living and Home Care, pages 216-223. Springer Berlin Heidelberg. 2012.
Toygun Basaklar, Yigit Tuncel, Shruti Yadav Narayana, Suat Gumussoy, and Umit Y. Ogras. Hyper- vector design for efficient hyperdimensional computing on edge devices. In Research Symposium on Tiny Machine Learning. 2021. URL https:: /ttp:::://////eeee/eeeeee net fotpfoorrmmiiddddeeeeeeaeaae
Alessio Burrello, Lukas Cavigelli. Kaspar Schindler, Luca Benini, and Abbas Rahimi. Laelaps: An energy-efficient seizure detection algorithm from long-term human ieeg recordings without false alarms. In 2019 Design, Automation and Test in Europe Conference and Exhibition (DATE), pages 752-757, 2019. doi: 2..2919/DAATE..219... 111111117717166666
Yu-Chuan Chuang, Cheng-Yane Chang, and Yeu Andy Wu. Dynamic hyperdimensional com- puting for improving accuracy-energy efficiency trade-offs. In 2020 IEEE Workshop on Signal Processing Systems (SiPS), pages 1-5, 2020.
Dheeru Dua and Casey Graff. UCI machine learning repository, 2017. URL http:/ttt:///rccie.e.eee uci. edu/ml
Paxon Frady, Denis Kleyko, and Friedrich Sommer. A theory of sequence indexing and working memory recurrent neural networks. Neural 145 1511 2018.
10

---

E. Paxon Frady, Denis Kleyko, Christopher J. Kymn, Bruno A. Olshausen, and Friedrich T. Sommer. Computing on functions using randomized vector representations, 2021.
William Fulton and Joe Harris. Representation theory: a first course, volume 129. Springer Science & Business Media, 2013.
Stephen Gallant and T. Wendy Okaywe. Representing Objects, Relations, and Sequences. Neural Computation, 25(8):2038 207000888777,,,,-- 08 2013. ISSN 0899-7667. doi: 10.1162/NECO a_00467.
Ross W Gayler. Multiplicative binding, representation operators & analogy (workshop poster). 1998.
Lulu Ge and Keshab K. Parhi. Classification using hyperdimensionall computing: review. IEEE Circuits and Systems Magazine, 20(2):30-47, 2020. ISSN 35880830. doi: 10.1109/mcas.2200.
2988388. URL http://dx:: doi wt.../...//.............. 2020. 2988388
Jan Gosmann and Chris Eliasmith. Vector-Derived Transformation Binding: An Improved Binding Operation for Deep Symbol-Like Processing in Neural Networks. Neural Computation, 31): 849-869. 05 2019. ISSN 0899-7667. doi: 10. 10.1162/neco_r cattisaa01119 URL.https://doi org 1162/neco_ 01179
Yunhui Guo, Mohsen Imani, Jaeyoung Kang, Sahand Salamat, Justin Morris, Baris Aksanli, Yeseong Kim, and Tajana Rosing. Hyperrec: Efficient recommender systems with hyperdimensional computing. Proceedings of the 26th Asia and South Pucific Design Automation Conference, ASPDAC 22, page 384-389, Association for Computing Machinery, 2021. ISBN 978145037999 doi: N0.1145/339488533435555
Saransh Gupta, Justin Morris, Mohsen Imani, Ranganathan Ramkumar, Jeffrey Yu, Aniket Tiwari, Baris Aksanli, and Tajana Rosing. Thrifty: Training with hyperdimensional computing across flash hierarchy. In 2020 IEEE/ACM International Conference On Computer Aided Design (ICCAD), pages 1-9, 2020.
Alejandro Hernandez- Cane, Namiko Matsumoto, Eric Ping, and Mohsen Imani. Onlinehd: Ro- bust, efficient, and single-pass online learning using hyperdimensional system. In 2021 Design, Automation and Test in Europe Conference and Exhibition (DATE), pages 56-61, 2021. doi:
10.23919/DATE51133 11W./D/TTT1139..... 090.1139.2.222..9. 22222022222999 202.99977......
J J Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings of the National Academy of Sciences, 79(8):2554 2558, 1982. ISSN 0027-8424. doi: 10.1073/pnas.79. 8.2544. URLhttps: /// /ww. pnas org/ cotteet/tent/////ccc// /0/////2555 8/2554
Itay Hubara, Matthicu Courbariaux, Daniel Soudry, Ran El-Yaniv, and Yoshua Bengio. Binarized neural networks. In Advances in Neural Information Processing Systems, 2016.
Mohsen Imani, John Messerly, Fan Wu, Wang Pi, and Tajana Rosing. A binary learning framework for hyperdimensional computing. In 2019 Design, Automation and Test in Europe Conference and Exhibition (DATE), pages 126-131. 20190 2a. doi: 10.23919/DATE.2000 2019.87198888
Mohsen Imani, Justin Morris, John Messerly, Helen Shu, Yaobang Deng, and Tajana Rosing. Bric: Locality-based based encoding for energy-efficiee brain-inspired hyperdimensional computing. In Proceedings of the 56th Annual Design Automation Conference 2019, pages 1-6, 2019b.
Mohsen Imani, Saikishan Pampana, Saransh Gupta, Minxuan Zhou, Yeseong Kim, and Tajana Rosing. Dual: Acceleration of clustering algorithms using digital-based processing in-memory. 2020 53rd Annual IEFE/ACM International Symposium Microarciteccuree (MICRO), pages 356-371, 2020. doi: 10. 1090000/0000666..222 202000006...0.00039
Mohsen Imani, Zhuowen Zou, Samuel Bosch, Sanjay Anantha Rao, Sahand Salamat, Venkatesh Kumar, Yeseong Kim, and Tajana Rosing. Revisiting hyperdimensional learning for fpga and low-power architectures. 202/ IEEE International Symposium on Architecture (HPCA), pages 221-234, 2021. doi: 10.109//PC
Computer
Gordon James, Martin W Liebeck, and Martin Liebeck. Representations and characters of groups. Cambridge University Press, 2001.

---

Pentti Kanerva. The spatter code for encoding concepts at many levels. In International Conference on Artificial Neural Networks, pages 226-229. Springer, 1994.
Pentti Kanerva. Hyperdimensional computing: An introduction to computing in distributed represen- tation with high-dimensional random vectors. Cogn. Comput., pages 139-159, 2009.
Pentti Kanerva et al. Fully distributed representation. PAT, 1(5):10000, 1997.
Yeseong Kim, Mohsen Imani, Niema Moshiri, and Tajana Rosing. Geniehd: Efficient dna pattern matching accelerator using hyperdimensionall computing. In 2020 Design, Automation and Test in Europe Conference and Exhibition (DATE), pages 115-120, 2020. doi: (0.23919/DATE48585
2020.9116397.
Denis Kleyko, Evgeny Osipov, Alexander Senior, Asad I Khan, and Yasar Ahmet Şekerciogglu. Holographic graph neuron: A bioinspired architecture for pattern processing. IEEE transactions on neural networks and learning systems, 28(6))1250-12622 2016.
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner. Gradient-based learning applied to document recognition. Proceedings of the IEEE, 86(11):228--2324 1998.
A. Mitrokhin, Sutor, C. Fermüller, and Y. Aloimonos. Learning sensorimotor control with neuromorphic sensors: Toward hyperdimensional active perception. Science Robotics, 4(30): eaaw6736, 2019. doi: 10.1 wttp://ciooboiiss.aaa77777
Peer Neubert and Stefan Schubert. Hyperdimensional computing as a framework for systematic aggregation of image descriptors, 2021.
Peer Neubert, Stefan Schubert, and Peter Protzel. An introduction to hyperdimensional computing for robotics. KI Künstliche Intelligenz, 33, 09 2019. doi: (0.1007/s13218-019-0006
T.A. Plate. Holographic reduced representations. IEEE Transactions on Neural Networks, 6(3): 623-641, 1995. doi: 10.1 10.1109/72.377968
Tony A Plate. Distributed representations and nested compositional structure. Citeseer, 1994.
Ali Rahimi and Benjamin Recht. Random features for large-scale kernel machines. In Proceedings of the 20th International Conference on Neural Information Processing Systems, NIPS'07, page 1177-1184, 2007. ISBN 9781605603520.
Frank Rosenblatt. The perceptron: probabilistic model for information storage and organization in the brain. Psychological review, 65(6))386, 1958.
Sahand Salamat, Mohsen Imani, Behnam Khaleghi, and Tajana Rosing. F5-hd: Fast flexible
fpga-based framework for refreshing typerdimensional computing. In Proceedings of the 2019 ACM/SIGDA International Symposium on Field-Pro Prold-PPograa Gate Arrays, FPGA '19, page 53-62. Association for Computing Machinery, 2019. ISBN 9781450361378. doi: 10.1145/ 3289602.3293913.
Pinaki Satpathy. Design and Implementation of Carry Select Adder Using T-Spice. Anchor Academic Publishing, 2016.
Kenny Schlegel, Peer Neubert, and Peter Protzel. comparison of vector symbolic architectures. Artificial Intelligence Review, Dec 2021. ISSN 1573-7462, doi: 10.100776104422001111110000 URL http: doi 1000110..000//1046666 121110222221010000--00001111-000 10110-3
Jean-Pierre Serre. Linear representations finite groups, volume 42. Springer, 1977.
Derek Smith and Paul Stanford. random walk in hamming space. 1990 IJCNN International Joint Conference on Neural Networks, pages 465 IEEE, 1990.
Anthony Thomas, Sanjoy Dasgupta, and Tajana Rosing. Theoretical foundations of hyperdimensional computing. 2020.
Jean-Philippe Vert, Koji Tsuda, and Bernhard Schölkopf. A primer on kernel methods. Kernel methods in computational biology, 47:35-70, 2004.
12

---

Jack E. Volder. The cordic trigonometric computing technique. IRE Transactions on Electronic Computers, EC-8(3):330-334) 1959. doi: 10.1109/EE.1959.522200
C. Wallace. suggestion for fast multiplier, IEEE Transactions on Electronic Computers, EC-13 (1):14-17, 1964. doi: 10.1 109/PGC. 1964.263830.
Han Xiao, Kashif Rasul, and Roland Vollgraf. Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms, 2017.
Checklist
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [N/A] This work will not be likely to have negative societal impact.
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? YYss]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [Yes]
(b) Did you include complete proofs of all theoretical results? [Yes]] Due to the page limits, the complete proofs are included in the supplementary materials.
3. If you experiments...
(a) Did you include the code, data, and instructions needed to reproduce the main exper- imental results (either in the supplemental material or as a URL)? [Yes] Code and instructions are included in the supplementary materials. Datasets can be MNIST and MNSHi which can downloaded online.
(b) Did you specify all the training details (e.g., data splits, hyperparameters, how they were chosen)? [Yes] The datasplit is default to each dataset. Other details are included in the paper.
(c) Did you report error bars (c.g., with respect to the random seed after running experi- ments multiple times)? [No] Due to the time limit, we did not include multiple runs for each experiment.
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, cloud provider)? [Yes]
4. If you are using existing assets (e.g., code, data, models) or curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [N/A] The datasets are public. We cited the source of the data.
(b) Did you mention the license of the assets? [N/A]
(c) Did you include any new assets either in the supplemental material or as a URL? [N/A]
(d) Did you discuss whether and how consent was obtained from people whose data you'l 're using/curating? [N/A] The datasets are public.
(e) Did you discuss whether the data you are using/curating contains personally identifiable information offensive content? [N/A] The datasets involved in this work do not have personal or offensive content. The content also discussed.
5. If you used crowdsourcing conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, if applicable? [N/A]
(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, if applicable? [N/A]
(c) Did you include the estimated hourly wage paid participants and the total amount spent on participant compensation? [N/A]
13


Reviews:
[{"review_id": "sMgF-Tm_bbk", "reviewer": "Reviewer_RVTb", "summary": "The authors present an analysis on vector symbolic architectures (VSAs) applied to canonical classification tasks. They comment on the variety of approaches in this space and provide some theoretical arguments for the limitations of hyperdimensional computing (HDC), a binary VSA. Finally, they propose a new form of VSA that maintains the desirable hardware compatibility while improving classification performance.", "questions": "1) I was confused about the methodology used for Table 1. Were the 1-epoch results for the proposed VSA models trained using SGD or bundling? Do you have a comparison for these two training methods?\n\n2) I think it would be valuable if the authors investigated the observation that VSA can perform better with a single pass of the training set than with multiple passes. Specifically, I think more effort should be made to convince the reader that this is a benefit of the model and not a shortcoming of the chosen optimization or model design process (e.g. a result of overfitting).\n\n3) I am curious to hear the authors’ perspective on how the similarity matrix relates to the classical outer-product memory used in Hopfield networks. \n\n4) typo on line 364 “VSA stikes a good trade”\n", "limitations": "The authors describe trade-offs for the various VSA algorithms throughout the text, although there is no explicit section naming limitations to their current approach. This would be a valuable addition to the paper.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 3, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality:** As far as I know the proposed group VSA & using the similarity matrix as an analysis of expressive capacity are novel contributions.\n\n**Quality:** The methods used are appropriate for their questions. I did not read the appendix to verify the claims.\n\n**Clarity:** The authors provided a pedagogical overview that covered the key ideas necessary to understand their contribution.\n\n**Significance:** I believe this work is a significant contribution towards reducing the exorbitant energy costs of popular classification algorithms (e.g. DNNs).\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "X5Nd4Ie8vdt", "reviewer": "Reviewer_tDsX", "summary": "The authors present a generalization of hyperdimensional computing which supports arbitrary finite groups as elements. They discuss representational power of classical VSAs, propose a novel initialization mechanism, describe their generalization both abstractly and with a concrete example (cyclic groups), and present accuracy results.", "questions": "(1) You describe the alternative conventional approach to improving accuracy as increasing $D$ (L35). Given that the space required for a group VSA scales with its group size and its CDC only logarithmically, it seems to imply that comparing a 10K-long HDC model with a 10K-long G($2^3$)-VSA model is giving the group VSA model an 8x advantage in resources (at vaguely similar CDC). What is the accuracy of an HDC with D of $2^3\\times 10000$ versus a 10K-long G($2^3$)-VSA? Same question for $2^4$.\n\n(2) Given the (welcomed) emphasis on establishing the unit cycle VSA within your group VSA generalization, I was a bit surprised not to see it in the results. I assume there's a good reason for this (i.e., is compute time absurd?), but given its prominence in the rest of the paper, I was wondering what that reason is. ", "limitations": "(Addressed in other sections.)", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "**Originality**\n\nThe paper's three main contributions (an anaylsis of expressivity of binary HDC, an approach to hypervector construction, and a generalized model of VSAs) all seem novel, somewhat orthogonal (and thus useful even in the absence of the other two), and applicable. The use of RFF for HDC is a meaningful adaptation of the idea, and group VSA (especially its concrete form over $\\mathbb{Z}/n\\mathbb{Z}$) is a clear and helpful extension of binary HDC.\n\n**Quality**\n\nThe analysis and development of RFF initialization and group VSA seems solid, well-motivated, and self-contained. The authors have struck a good balance between capturing high-level concepts (motivation by similarity matrices in Def 1; arbitrary VSAs in Def 2) and concrete applications of them (counterexample $\\textrm{M}_{\\textrm{Lemma4.1}}$; cyclic group VSAs in 6.2). I appreciated having both aspects developed in parallel.\n\nSection 7 seemed overly brief. While the motivating problem seems clear enough, though perhaps it would've been helpful to understand the efficacy of the approach in avoiding the problem and/or the effect of number of epochs.\n\nThe results seem to suggest that nearly all of the accuracy benefits stem from RFF initialization. The practical benefits of group VSA seem limited, if not a bit mixed. I still think the contribution of a generalized formulation of group VSA is useful regardless, but it would have been nice to see some discussion as to why the extra representational power doesn't translate to much better accuracy.\n\nThe CDC analysis was a welcomed addition. Given the importance of an efficient hardware implementation as a motivation for the existence of HDC, I appreciated the nod to fleshing out the proposal of group VSA with the impact to its implementation.\n\n**Clarity**\n\nThe writing is clear, and most of the paper flows well from one section to another. Analysis leads naturally to proposals, and most sections progress from abstract to concrete in a clean and understandable way.\n\n**Significance**\n\nThis paper seems like a solid addition to the body of work on HDC. Its contributions each stand on their own and form a solid foundation for further work. It seems easy to build off, self-contained and methodical in its approach, and useful for understanding the behavior of HDC.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "PM0Xv8ExSb8", "reviewer": "Reviewer_y6Vm", "summary": "The authors present a new measure of learning ability (expressivity) for any vector symbolic architecture (VSA) based on similarity matrices. Specifically, if any VSA (including HDC) cannot express a specific similarity matrix, corresponding to the optimal solution of a learning problem, then the VSA cannot converge to the optimal solution for the learning problem. Using this concept of expressivity, the authors highlight that HDC vectors of any large dimension cannot express certain similarity matrices. Further, they demonstrate that HDC vectors initialized with random Fourier features have higher expressivity than randomly selected ones which in turn results in higher accuracy on MNIST (image-classification task). Lastly, the authors define group VSAs which extends HDC to hypervectors that have much higher expressivity (and accuracy on MNIST/Fashion MNIST image classification tasks). ", "questions": "Kindly address questions discussed in Strengths and weaknesses section.", "limitations": "The authors can make note that the proposed SGD training for HDC and group VSA models might be more energy consuming than existing HDC learning (single pass). Further, the group VSA hardware implementation is notably costlier than binary HDC. ", "rating": 7, "confidence": 2, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "The paper presents a good survey of prior art and highlighting how the results of this paper are novel as they present a theoretical formulation of how to assess the limitations of HDC hypervectors compared to other VSAs. \n\nThe authors do a good job of defining all functions/params which helps improve the readability of the paper despite the detailed mathematical discussion.\n\nSection 8 shows good results confirming the expectation that RFF improves HDC performance while the group VSA’s continue to improve it further. It is interesting that the accuracy improvement achieved with group VSA hypervectors is much smaller, as I would have expected otherwise considering the much higher learnability of group VSAs. It would be interesting if the authors can add data for another learning task (aside from the Bayes-optimal classifier) where HDC (RFF/otherwise) is unable to learn the optimal result or has a much poorer accuracy.\n\nSection 8.1 tries to assess the hardware cost of implementing the different HDC/VSA approaches. For binary HDC, the authors select a ripple-carry adder, it’s unclear why they didn’t choose parallel adder circuits like carry select adder which has lower depth and could have made the HDC implementation further cheaper. While CDC metric captures the latency and hence performance aspect of the cost, measuring the change in number of operations might be a more realistic estimate of the energy/area penalty incurred on actual hardware. Since higher complexity group VSA’s will require a much larger number of ops for small accuracy improvements for certain tasks. \n\n It is useful that the authors have plotted the accuracy vs CDC tradeoff in Figure 1, I was curious if combining with efficient hardware design approaches like Basaklar et. al., [2021], could help lower the CDC for both HDC and group VSAs by reducing the number of elements in each hypervectors (currently 10k). This in turn might help establish group VSA’s as more accurate for a given hardware cost. \n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "LXj0HIISVIi", "reviewer": "Reviewer_s9Zr", "summary": "Hyperdimensional computing is an emerging learning paradigm with two main thrusts attempting to improve its accuracy to match SOTA (DL) methods: the first focussed on longer binary vectors and the second on increasing complexity of vector elements (e.g. floating point, complex numbers). The second is often referred as Vector Symbolic Architecture (VSA). The paper introduces the notion of expressivity of VSA as the similarity matrices that can be represented (this is closely linked to learnability). It argues that VSA with more complex hypervectors is more expressive than HDC with binary hypervectors of any dimension.  It proposes a new initialization of binary hypervectors using random Fourier features. ", "questions": "Are there other notions of similarity different from inner product that could yield different results with respect to expressiveness of the hypervectors or is the result independent of how we define similarity? \n\nLemma 4.1 is interesting but could authors provide an intuition for the class of matrices that binary HDC cannot express?", "limitations": "There are no potential negative societal impact of this work to the best of this reviewer's understanding. ", "rating": 7, "confidence": 3, "soundness": 3, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "+ The paper defines a notion of expressiveness using similarity matrices and studies the expressiveness of HDC with complex hypervectors vs longer hypervectors.\n\n+  The proposes a new initialization of binary hypervectors using random Fourier features, and shows an improvement by 6.4% on MNIST classification.  \n\n+ A new group VSA is defined which is more complex than binary hypervectors but less than floating-point. This improves MNIST accuracy by an addition 1.2%.\n\nStatement 4.1 is a bit confusing. The second statement says that any VSA that can express M can learn this task - that seems to be tautological (if no VSA can express M, the statement will hold vacuously). It would be better to characterize some VSA can express M and learn it. ", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept