Efficient Hyperdimensional Computing
Authors: Zhanglu Yan
Shida Wang
Kaiwen Tang
Weng-Fai Wong
Venue: Submitted to ICLR 2023 (2023)
Keywords: Hyperdimensional computing

Abstract: Hyperdimensional computing (HDC) uses binary vectors of high dimensions to perform classification. Due to its simplicity and massive parallelism, HDC can be highly energy-efficient and well-suited for resource-constrained platforms. However, in trading off orthogonality with efficiency, hypervectors may use tens of thousands of dimensions. In this paper, we will examine the necessity for such high dimensions. In particular, we give a detailed theoretical analysis of the relationship among dimensions of hypervectors, accuracy, and orthogonality. The main conclusion of this study is that a much lower dimension, typically less than 100, can also achieve similar or even higher detecting accuracy compared with other state-of-the-art HDC models.  Based on this insight, we propose a suite of novel techniques to build HDC models that use binary hypervectors of dimensions that are orders of magnitude smaller than those found in the state-of-the-art HDC models, yet yield equivalent or even improved accuracy and efficiency. For image classification, we achieved an HDC accuracy of 96.88\% with a dimension of only 32 on the MNIST dataset. We further explore our methods on more complex datasets like CIFAR-10 and show the limits of HDC computing.

Under review as a conference paper at ICLR 2023
EFFICIENT HyPerDIMeNSIONAL COMPUTING
Anonymous authors
Paper under double-blind review
ABSTRACT
Hyperdimensional computing (HDC) uses binary vectors of high dimensions perform classification. Due to its simplicity and massive parallelism, HDC can be highly energy-efficient and well-suited for resource-constrained platforms. How- ever, in trading off orthogonality with efficiency, hypervectors may use tens of thousands of dimensions. In this paper, we will examine the necessity for such high dimensions. In particular, lationship among dimensions of hypervectors, accuracy, and orthogonality. The main conclusion of this study is that much lower dimension, typically less than 100, can also achieve similar or even higher detecting accuracy compared with other state-of-the-art HDC models. Based this insight, propose suite of novel techniques to build HDC models that use binary hypervectors of dimensions that are orders of magnitude smaller than those found in the state-of-the-an HDC models, yet yield equivalent or even improved accuracy and efficieney!] For im- age classification, we achieved an HDC accuracy of 96 88% with dimension of only 32 on the MNIST dataset. We further explore our methods on more complex datasets like CIFAR-10 and show the limits of HDC computing.
give detailed theoretical analysis of the re-
INTRODUCTION
Hyperdiienssoonal computing (HDC) is emerging learning paradigm inspired by an abstract rep- resentation of neuron activity in the human brain using high-dimensional binary vectors. Compared with other well-known training methods like artificial neural networks (ANNs), HDCs have the ad- vantage of high parallelism and low energy consumption (low latency). This makes HDCs well suited resource-constrained applications such as electroencephalogran detection, robotics, lan- guage recognition and federated learning (Hsieh et al. [2021] Asgarinejad et 20. et al., 2019 Rahimi et al. 2016). HDCs are also easy to implement in hardware (Schmuck et al. 2019
Salamat et al. 20199)
Unfortunately, the practical deployment of HDC suffers from low model accuracy and always restricted to small and simple datasets. To solve the problem, commonly used technique is in- creasing the hypervector dimension (Neubert et al. 2019) Schlegel et al. 2022 Yu et al.) 2022). For the MNIST dataset, hypervector dimensions of 10,000 often used. Duan et al. (202)) and Yu et al. (2022) achieved the state-of-the- art accuracies of 94.74% and 95.4% sep- arately this way. In these and other state-of-the-an HDC works, hypervectors
example, running
randomly drawn from the hyperspace 1-1, =1j4, where the dimension d is very high. This ensures high orthogonal- ity, making the hypervectors more independent and easier to distinguish from each other (Thomas) et al. 2020). As a result, accuracy is improved and more complex application scenarios can be tar- geted. However, the price paid due to higher dimension in higher energy consumption possibly negating the advantage of HDC altogether (Neubert et al. 2019 This paper addresses this tradeoff.
In this paper, we will analyze the relationship between hypervector dimension and accuracy, as well as between dimension and orthogonality. In our analysis, we found that strict orthogonality can be obtained for small d. We will show that a dimension of only 2 2 n] is sufficient to yield vectors in (-1, 1]d with strict orthogonality. Dimensions higher than that are not necessary. If we relax orthogonality to
(Kainen & Krkova| (020). we will show that it is even easier to construct the hypervectors. Further, it is intuitively true that high dimensions will lead to high orthogonality (Thomas et al. 2020), contrary to popular belief, we found that as the

---

Under review as a conference paper at ICLR 2023
dimension of the hypervectors d increases, the upper bound for inference accuracy actually decreases (Statement 3.1 and Statement 3.2). In particular, if the hypervector dimension sufficient to represent vector with K classes (d log2 K) then, the lower the dimension, the higher the accuracy. The key insight our work is this: In HDC, it is not the higher dimension, that is the determinant of accuracy, and the required orthogonality for given problem be achieved at lower hypervector dimensions using our proposed techniques.
Based on the analysis, we propose combination of novel trainable binary kernel-based en- coder with the majority rule (shown in Figure 3 to reduce the hypervector dimension signifi- cantly while maintaining state-of-art accuracies. Rumning on the MNIST dataset, HDC accuracies of 96.88/97.233 .3%% were achieved with hypervector dimensions of only 32/64. The total number of calculation operations of our method is a mere 7% of the previous state-of-art related works where hypervectors dimensions of 10,000 more were needed. We further explored our methods on CIFAR- 10 and an HDC accuracy of 46.18g 16%18% was achieved. Both our analysis and experiments show that dimensions of 5,000 even 10,000 used by the state-of-the-art in HDC are not necessary.
The contribution of this paper is as follows:
We give comprehensive analysis of the relationship between hypervector dimension and the accuracy of HDC. Both the worst-case and average-case accuracy are studied. Mathe- matically, explain why relatively lower dimensions can yield higher model accuracies. This contradicts the standard assumption HDC. Furthermore, relationship between orthogonality and hypervector dimension is also discussed. Based on the analysis, we can reduce the dimension by nearly three orders of magnitude.
We introduce kernel-based binary encoder and two HDC retraining algorithms. With these techniques, we can achieve higher detection accuracies using much smaller hyper- vector dimensions (latency) and better orthogonality compared to the state-of-the-art.
This paper is organized as follows. First, the basic workflow and background of HDC are introduced. Then, describe main dimension-accuracy and diimension-orthognaalii analysis in Section 3 In Section 4 we present trainable binary encoder and two HDC retraining approaches improve accuracy while the same time reducing energy consumption. We then show our experimental results and comparison with state-of-the-at HDCs in Section [ followed by a discussion and conclusion.
Organisation
BACKGROUND
Hyperdimensional computing encodes binary hypervectors with typical dimensions of 5,000 to 10,000 to represent the data. Using the MNIST dataset as an example, HDC encodes one float32- type image f fo, f1,-.., f783 hypervectors by binding and adding the value hypervectors and position hypervectors p together. Both these two hypervectors are independently drawn from the hyperspace {-1, +1]4 randomly. Mathematically, we can construct representation for each image as followed:
sgn (11 X Pfo + X Pfa + ... Usas X PPrrea)
where sgn(-) is the sign function that binarizes the sum of hypervectors and returns -1 or 1. sgn(O) randomly assigned -1. X is the binding operation that perform coordinate-wise (element- wise) multiplication. For example, [-1, 1, - 11, -1] = 1,
For training, all hypervectors F1, ..., 760,000 that of the same digit are added together. The majority rule is then used to generate the representation R, for class c
R. sgn
Σ r
For inference, the encoded test image compared with the representation of each class R., and the most similar one is selected. Cosine similarity, 1.2 distance, and Hamming distance commonly
2

---

Under review as a conference paper at ICLR 2023
used similarity measures in previous works. According to Frady et al. (2021), the inner product has the same function with Hamming distance for binary hyper vectors with values of -1 and 1, which used in this work. The workflow is shown in the Appendix A.3
HIGH DIMENSIONS ARE NOT NECESSARY
Compared to traditional ANNs, the use of binary vectors and simple, point-wise computation in HDC holds the promise of low energy consumption while achieving competitive accuracies. The Achilles Heel is in the high dimensions needed that potentially negated the gains. In this section, we will study the need for high hypervector dimensions terms of both accuracy and orthogonality.
Through an analysis of the relationship between dimension and accuracy, we will show that a higher hypervector dimension does not necessarily lead higher accuracy. We will show that for a classifi- cation task that has only two classes, a higher hypervector dimension results in both lower worst-case and average- case accuracy.
We then study the relationship between dimension and orthogonality and show that good orthogo- nality does not require high dimensions. This opens the door to performing HDC with significantly lower dimension hypervectors.
3.1 DIMENSION-ACCURACY ANALYSIS
To simplify the analysis of the HDC, consider the following assumptions of hypervectors without loss of generality. We assume that the hypervectors are uniformly distributed over a d-dimensional unit ball:
X {ar E R ||||| S 1}.
Moreover, we assume that hypervectors x are linearly separable and each class with label can be represented by Ci:
C {x x - 0,
1 1sisk
where 0, [0, 1jd support hypervectors that used distinguish classes i from other classes. This is a reasonable assumption as long as we select sufficiently large so that there exists a mapping (encoder) to embed the raw data into d-dimensional unit ball.
Similarly, we define the prediction class C₁ by 0, as followed:
Ć; = {u E X x 03 I.j + it, 1sisK.
When we apply the majority rule to separate the above hypervectors x, we are approximating 0, with 0 in the sense of maximizing the prediction accuracy. Here each 0; E {0, 1]d is a binary vector.
Therefore we define the worst-case K-classes prediction accuracy over hypervectors distribution X in the following expression:
Acck, = inf
sup
Ex
Σ
II j$
(0.-020, (0.2200aa))
or. 0x. 8x 0 01.02.....0
Statement 3.1 Assume K 2, as the dimension of the hypervectors d increases, the worst-case prediction accuracy decreases with the following rate:
Acc
inf sup Ex 1 1 x> 0,,0 8.88 8,
(0) 0z) 16, 02) 110 021121 0olla
arccos(
= inf sup 0, 0, arccos(
E (VJ T
d +
π
2'
3

---

Under review as a conference paper at ICLR 2023
1.00
1.00
0.99
0.95
0.98
0.90
Accuracy
0.97
0.85
0.96
0.95
0.94
0.75
0.93
0.92
0.70
200
400
600
800
1000
0
200
400
600
800
1000
Dimension
Dimension
Figure 1: Worst-case Accuracy Acc
Figure Average-case Accuracy Acc2,d
The first equality is by the symmetry of distribution expectation over X and the detail is given in Lemma A.1 For the third equality, the proof is given in Lemma A.3 and Lemma A.4
The second equality is the evaluation of
In the next statement, further consider the average-case. Assume the prior distribution P for 0.....0x ~ (0 119. We can define the average accuracy in the following expression:
ACck,d Eo, Ox
sup
Eg
EII
(0,0)0;2) (6, (b.n)0)a)) i=1
8, 02....00
Statement 3.2 Assume K = 2, the dimension of the hypervectors d increases, the average case prediction accuracy decreases:
Acck,a = Eo, 02,0000000111 sup E, 0,
1 (01-2200:2) ( (22
(01 - (2) -82) 100 - 02 1a 1a116, - 02112
arccos(
00000110000111 sup 6 0,
arccos ( (sup)
Ei 10, -0al:o) v
02
Here 101 O2](3) denotes the i-th maximum coordinate for vector 00
62)-
As the exact expression for the average-case accuracy is harder to evaluate, do the Monte Carlo simulation which sampling 0 and 0g 1000 times to evaluate the expectation form. We then show the curve of Ace and Acek,a af over dimension from to 1000 in Figure and 22 It is easy to find that high dimension for HDCs is not necessary for both the worst-case and average-case, the upper bound of accuracy will drop slowly when the dimension increases.
According Tax & Duin (2002), we can approximate multi-class case where K by one- against-one binary classification. Therefore, we define the quasi-accurace of K K-class classification as follows:
Σisj Acc 2d
Quasi-AccK,
K(K 11)
where Acctya can either the average-case or worst-case accuracy that distinguishes class and j. Since the accuracy Acctj for binary classification decreases the dimension increase, the quasi- accuracy follows the same trend.
4

---

Under review as a conference paper at ICLR 2023
3.2 DIMENSIO--ORTHOGONAAN ANALYSIS
For strict orthogonality, we first construct a Hadamard matrix sequence {Hz) followed:
(Horadam 2012) as
Ho [1];
Ho
Ho
H1
Ho
-Hl
:
Hg-1 H₂ H H
Hg-1
According to the definition of Hadamard matrix, if we take rows from [log,n) m| we find hy- pervectors with strict orthogonality 2 2[log, n1 -dimmensioo space, Then, we can give the following statement:
Statement 3.3 Dimension d of only 2 m1 is needed to find n strictly orthogonal hypervectors, which indicates the unnecessity of high dimension.
Further, if the Hadamard conjecture (Horadam) 2012) holds (for each positive integer k, there exists a Hadamard matrix order 4k), the number can be bounded above by + 3.
We then consider the quasi-orthogonality since there is enforcement of strict orthogonality in HDC's practice.
Definition 3.1 (e-qqusiorthhogonalit) For two unit vectors and we call them quasi- orthogonal:
l y S.
Based the definition and recent progress quasi-orthogonality (Kainen & Krkova 2020) (shown in I.I) we can draw the following conclusion:
Statement 3.4 If orthogonnalit has been relaxed e-quasiorthognnality for E (0, 1), the number of d-dimension vectors with e-quasiorthooonalliy is exponential with respect to the dimension:
((e(())d)
Here c(E) is constant related to E.
Both Statement 3.3 and 3.4 indicate that even in the low dimension case, it is still feasible to find hypervectors with high quass-)orthooonaaityy
METHODS
As shown in Figure we first combine a kernel-based binary encoder with a fully-connected layer and train the whole network with cross-entropy loss function. Since the whole structure is binary, the straight-throug fully-connected layer is replaced with majority rule for power-saving. Weight sharing indicates that we use the same weights before and after we replacing the FC layer with the majority rule. Then, representations of each class R. be obtained with Equation [ To improve R., train the combination of the binary encoder and majority rule with STE (Algon [Algorithm@ Step 1) and recompute the final representations R. of each class c. Finally, all hypervectors are trained with Algorithm Step 2 for higher detection accuracy.
estimator (STE) (Bengio et al. 2013) is used for pack-propagation. Next, the
4.1 BINARY KERNEL-BASHR ENCODER
The binary kernel-based encoder is composed of binary neural netwrok (BNN) style layers. Unlike the standard BNNs whose input is in floating point numbers, both the input and activation values

---

Under review as a conference paper at ICLR 2023
Training
Inference
Training Data
Training Data
Training Data
Testing Data
Eacoder
Layer
Weight
Froze Enoader
Enzoder
Transfering
Majerity Rulo
Ri
Majority Rale
FC
Voctor R
Remmet +
HyperVector
Vector R
Ravvyy
Similarty Check
Vector Rt
RC
R
Figure 3: Workflow of Our HDC.
used in our structure have been quantized to and Since the information transmitted among layers is binary, we can replace the multiplication operations with addition operations. In particular, we only need to sum up the weights whose corresponding inputs are 1. Weights whose corresponding inputs are O can be ignored. For each neuron i at layer if the sum up if higher than 1, '1' is output. Otherwise, we output 0, Mathematically..
b/) s jj=o 1- + b/) >
(2)
1,
where of indicates the output of layer at neuron i, wh, and bf indicates the weight and bias at layer (j is the index of neurons in 1 layer, and is the neuron index at th layer.), Wijj indicates the weight whose corresponding inputs æ;-1 are 1.
G(x)) is the gradient for the backpropagation. However, because the whole function is not continuous and not differentiable at the turning points, we use the method of the straight-through estimator to simulate the gradient. Thus G(z)) is set as make the whole network trainable: G(xx) 1.
After the training, we remove the fully connected layer and run the encoder to generate the binary representation R. of each class. The majority rule is used here, shown in Algorithm
Algorithm representation Generation:
Algorithm HDC Retraining:
Require: number of training data Ensure: Trained binary encoder E; Repre- sentation Rg for class e with dimension of d;Binary Representation R² Outputs of encoder z/: Pre-defined Threshold A;
Require:
Training data x with label R.;
Trained Encoder E; N training epochs.
1: Step1:
2: for epoch- 1 N do
3: y= E(x))
1: y F(x); R. = 0
L= =mmeeyy, Rt //Bp: STE
2: for i to do
5: end for
3: R. + Ve
4: end for
6: Step2:
5: for i = 1 to d do
7: y = E(x)
6:
if [ > then
8: if y! Reb then
7:
R
9:
Recorrec + = Ir*
8:
else
10: Rewrong
1r *
9:
R 0
11: end if
10:
end if
12: Generate Rd (Algorithm line 5-9)
end for

---

Under review as a conference paper at ICLR 2023
4.2 RETRAINING
Here, we introduce a two-step retraining method. As shown in Algorithm 2 training data are first sent the encoder in batches. The mean squared error is used as the loss function to update weights in the encoder. Then, we freeze the encoder and update the representation of each class. If the output y wrongly detected as class Curong which should belong class Coorrect. we minus the representation of wrong class Rewrong by the multiplication of learning rate and y. Meanwhile, we add the representation of the correct class Revigne by the multiplication of the learning rate and y as well. Then, the modified Re are sent to Algorithm
generate the binary representation E.
4.3 INFERENCE
As we have already computed the representation of each class, we can simply compare the similarity between the resulting hypervector (computed by sending the test data to the same encoder) and the representation of all classes. Then, we output the class with the highest similarity. We turn the value of 0 in R to -1 and do the inner product for similarity check. Orthogonality of the resulting representation R. can be evaluated with Equation orthogonality.
The closer Ô is 0, the better the
R * R T
0
(3)
K(K 1)
d
01
RESULTS
We have implemented schemes in CUDA-accelerated (CUDA 11.7) PyToorc version 1.13.0. The experiments were performed on an Intel Xeon E5-2680 server with two NVIDIA A100 Tensor Core GPUs and one GeForce RT 3090 GPU, running 64-bit Linux 5.15. MNIST datase and CIFARI are used in our experiments.
5.1 A CASE STUDY OF OUR TECHNOLOGIES
Here, we will describe how our approaches improve the digit recognition task step by step.
5.1.1 TRAINING THE ENCODER
We build a three-layer binary kernel-based encoder to enhance the HDC model. For each layer, we set the output channel number 32, kernel size 6, and stride 2.
We first discuss the relationship between the pre-defined threshold mentioned Algorithm | with accuracy. As shown in Figure running on the MNIST dataset, taking the hypervector dimension of 16 as an example (full ablation studies are shown in the Appendix), we find that the threshold has good robustness against the noise. The detection accuracy remains almost the same when the threshold varies from 500 to 5000 (the max number in Ri after encoder without majority rule is around 6500) and good orthogonality is also achieved.
We further consider the relationship between the dimension and inference accuracy with the most suitable threshold. As shown in Figure [5] we can achieve an HDC accuracy of 96.822.88 06.82/77.23% with a dimension of only 32 and 64. Also, the accuracy will drop when the dimension is higher than 128, which is consistent with Statement
5.1.2 HDC RETRAINING
Thus far, we have shown how we can achieve the-state-of-at HDC accuracy with the smallest hy- pervector dimension. We can in fact improve the results using retraining techniques we will describe this section. For example, with dimension of 32, we can push the accuracy 96.88 66.88 with our
hhtt:://yanmllccmm. https://www.c.. toronto.ooooooooo krizleifar.hml

---

Under review as a conference paper at ICLR 2023
120
68
07.24
97.53
57.44
100
100
05.47
05:65
95.65
95.65
95.65 95.57
96
D6.12
25.50
Percertage (N)
80
73.15
544
76.25
Accuracy
orthogonnality
52
60
90
40
30,65
$1.55
29.14
Truined Ereeder ICIMM)
Tralined Eneeder Sanjeity Rade
80.25
33:25
29.15
29.75
29.75
29.75
28.5
66
84
9.8
122
200
16
128
256
1024
2048
Throshold
Figure 4: Threshold Study. The orthogonality is measured using Equation
Figure 5: Dimension Study
two-step training (0.05% and 0.01% % accuracy improvement with steps and 2, respectively). How- ever, shown in Figure there is almost no accuracy drop after replacing the fully-connected layer with the majority rule, which indicates accuracy improvement after retraining may not be signifi- cant for the MNIST datasets. Therefore, we will explore our retraining methods on the CIFAR-10 dataset. Using the same hypervector dimension, a baseline accuracy (trained encoder+majority rule) of 38.42% was achieved. After retraining step 1 and step 2, the accuracy has improved by 0.21% % and 0.42% respectively. The final accuracy increased to 39.05% in matter of minutes.
5.2 EXPERIMENTAL RESULTS
Our full set of experiment results is shown in Table [ where compare accuracy, dimension, and number of operations with other state-of-the-art HDC models. In this paper, HDC accuracies of 96.88% and 97. 97.23% with d 32 and 64 were achieved for the MNIST dataset. We also applied our techniques to a larger dataset to test whether they work in more complex situations. For the CIFAR- 10 dataset, an HDC accuracy of 39.05% with d 32 was achieved with 1.17M computations. When we increase the dimension to 128, we can achieve an HDC accuracy of 46.16666 18% with 4.34M computations.
A number of state-of-the-arr HDC works were chosen for comparison. TD-HDC, proposed by Chuang et al.] (2020), is threshold-baser framework to dynamically choose an execution path. They can improve the accuracy-enery. efficiency trade-off and achieve an HDC accuracy of 88.92% on MNIST with their pure binary HD model. Hassan et al. (202T) used basic HDC model on the MNIST dataset in their
study. They encoded the pixels based their black/white value and used majority sum operation in the training stage to combine similar samples. They achieved an HDC accuracy of 86% the MNIST dataset. HDC is also used in federated learning and secure learning. FL-HDC by [Hsieh et al. (2021) focused on the combination of HDC and federated learn- ing. They introduced the polarized model into the federated learning field to reduce communication costs and managed to control the accuracy drop by retraining. 88% accuracy was achieved on the MNIST dataset. SecureHD (Imani et al., 2019b) adapted novel encoding and decoding method to perform securely learning tasks with the idea of HDC. Their accuracy on the MNIST dataset was 95% for federated training. More recently, LeHDC (Duan al., 2022), by transferring the HDC classifier into the binary neural network, has used the learning-based HDC to achieve 94. 74% on the MNIST dataset and 46. 10% on the CIFAR-10 dataset. QuantHD (Imani et al. (019a) and SearcHD Imani et al. 2019c) are two methods that introduce multi-model and retraining into the HDC field. In LeHDC, they report the accuracy the CIFAR-10 dataset with the methods of QuantHD and SearcHD baselines, which are 22.66% and 28.42%. Compared with HDC, binary neural net- works always require additional multiplication operations at least in the first layer because of the floating point input, which is much more expensive and was not considered in comparison.
For inference, cosine similarity and Hamming distance are used in most saute-of-the-ee works. Since cosine distance requires additional multiplication and division operations which are quite expensive,
8

---

Under review as a conference paper at ICLR 2023
chose Hamming distance instead. The number of operations in Hamming distance is linearly proportional to the dimension of the hypervectors, which indicates that our method only needs 0.32% operations compared with other HDCs with dimension of 10,000.
Table 1: Comparison with related works.
Inference Encoder addition/Boolcan op count
Accuracy
Dimension
Similarity
MNIST
SearcHD
84.43%
10,000
7.84M/7.8 7.84//.84M
Hamming
FL-HDC
88%
10,000
7.84M/7.841
Cosine
TD-HDC
88 88.92%
5,000
3. 3.92M/3.92M
Hamming
QuantHD
89. 59.28%
10,000
7.84M/7.84X
Hamming
LeHDC
94.74%
10,000
7. 7.84M/7.844
Hamming
Se
95%
10,000
7.84M/7 8.4
Cosine
This work
96.88%
32
1.15M/0
Hamming
This work
97.23%
64
1.19M/0
Hamming
CIFAR-II 10
SearcHD
22.66%
10,000
10,24M/10.24N
Hamming
QuantHD
28.42%
10,000
10.24M/10. 24M
Hamming
LeHDC
46.10%
10,000
10.24M/100.4N1
Hamming
This work
39.05%
32
1.17M/0
Hamming
This work
46.18%
128
4.34M/0
Hamming
6 DISCUSSION
Our analysis of the relationship between orthogonality and the number of classes also affects the results. This has been largely ignored in other HDC works. Taking the MNIST dataset as ex- ample, the -tate-of-the-art works use hypervectors of dimensions 5,000 to 10,000 to 'distinguish' pixel values that range from 0 to 255. However, if quantization is applied input data and proper encoder is used to extract the information from the original picture, theoretically, a much smaller dimension (K reduced 10 because the MNIST dataset has 10 labels) needed. This also explains why our method and other HDCs cannot work on more complex datasets like ImageNet where the number classes large.
CONCLUSION
In this paper, considered the dimension of the hypervectors used in HDC. We presented a detailed analysis of the relationship between dimension and accuracy as well as the relationship between dimension and orthogonality to demonstrate that it is not necessary to use high dimension to get good performance in HDC. We showed that it is the orthogonality that affects accuracy. Previous works have been using high dimensions to achieve higher orthogonal because they used randomly drawn hypervectors. We showed that the orthogonality required to solve the problem can be achieved without resorting to high dimensions. As result, can reduce the dimensions from the tens of thousands used by the state-of-the-art to merely tens, while achieving the same level of accuracy. Computing operations during inference have been reduced Running on the MNIST dataset, we achieved an HDC accuracy of 96.88% using dimension of only 32, All our results are reproducible using the code we have made public.
tenth of that in traditional HDCs.
REFERENCES
Fatemeh Asgarinejad, Anthony Thomas, and Tajana Rosing, Detection of epileptic seizures from surface EEG using hyperdimensional computing. In 2020 42nd Annual International Conference of the IEEE Engineering in Medicine & Biology Society (EMBC), pp. 536-540. IEEE, 2020.
Yoshua Bengio, Nicholas Léonard, and Aaron Courville. Estimating or propagating gradients through stochastic neurons for conditional computation, 2013.

---

Under review as a conference paper at ICLR 2023
Yu-Chuan Chuang. Cheng- Yang Chang, and An- Yeu Andy Wu. Dynamic hyperdimensional com- puting for improving accuracy-energy efficiency trade-offs. In 2020 IEEE Workshop on Signal Processing Systems (SiPS), pp. 1-5. IEEE, 2020.
Shijin Duan, Yejia Liu, Shaolei Ren, and Xiaolin Xu. LeHDC: Learning- hyperdimensional computing classifier. arXiv preprint 2tt.:22233968800 2022.
E Paxon Frady, Denis Kleyko, Christopher J Kymn, Bruno A Olshausen, and Friedrich T Sommer. Computing on functions using randomized vector representations. arXiv preprint arXiv:2109.03422 2021.
Eman Hassan, Yasmin Halawani, Baker Mohammad, and Hani Saleh. Hyper-dimensional comput- ing challenges and opportunities for Al applications. IEEE Access, 2021.
Kathy Horadam. Hadamard matrices and their applications. Princeton University Press, 2012.
Cheng- Yen Hsich, Yu-Chuan Chuang, and An-Yeu Andy Wu. FL-HDC: Hyperdimensional comput- ing design for the application of federated learning. In 202/ IEEE 3rd International Conference on Artificial Intelligence Circuits and Systems (AICAS), pp. 1-5. IEEE, 2021.
Mohsen Imani, Samuel Bosch, Sohum Datta, Sharadhi Ramakrishna, Sahand Salamat, Jan M Rabaey, and Tajana Rosing. QuantHD: A quantization framework for hyperdimensional com- puting. IEEE Transactions Computer-Aides Design of Integrated Circuits and Systems, 39 (10):2268-22) 2019a.
Mohsen Imani, Yeseong Kim, Sadegh Riazi, John Messerly, Patric Liu, Farinaz Koushanfar, and Tajana Rosing. A framework for collaborative learning in secure high-dimensional space. In 2019 IEEE 12th International Conference on Cloud Computing (CLOUD), pp. 2019b.
IEEE,
Mohsen Imani, Xunzhao Yin, John Messerly, Saransh Gupta, Michael Niemier, Xiaobo Sharon Hu, and Tajana Rosing. SearcHD: A memory-centrie hyperdimensional computing with stochastic training. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 39 (10):2422-244) 2019c.
Paul C Kainen and Vera Krkova. Quasiorthogonal dimension. In Beyond Iraditional probabilistic data processing techniques: Interval. fuzzy etc. Methods and their applications, pp. 615-629, Springer, 2020.
Peer Neubert, SteKanervafan Schubert, and Peter Protzel. An introduction to hyperdimensional computing for robotics. KI-Känstliche Intelligenz, 33(4):319-330, 2019.
Abbas Rahimi, Pentti Kanerva, and Jan M Rabacy. A robust and
classifier using brain-inspired hyperdimensional computing. In Proceedings of the 2016 international symposium on low power electronics and design, pp. 64-69, 2016
Sahand Salamat, Mohsen Imani, Behnam Khaleghi, and Tajana Rosing. F5-HD: Fast flexible
FPGA- based framework for refreshing hyperdimensional computing. In Proceedings of the 2019 ACM/SIGDA International Symposium on Field- Programmable Gate Arrays, pp. 53 62, 2019. 52-62,
Kenny Schlegel, Peer Neubert, and Peter Protzel. A comparison of vector symbolic architectures. Artificial Intelligence Review, 55(6))4523-4555 2022.
Manuel Schmuck, Luca Benini, and Abbas Rahimi. Hardware optimizations of dense binary hy- perdimensional computing: Rematerialization of hypervectors, binarized bundling, and combi- national associative memory. ACM Journal on Emerging Technologies in Computing Systems (JETC), 15(4):1-25. 2019.
David MJ Tax and Robert PW Duin. Using two-class classifiers for multiclass classification. In 2002 International Conference on Pattern Recognition, volume 2, pp. 124-127. IEEE, 2002.
Authony Thomas, Sanjoy Dasgupta, and Tajana Rosing. Theoretical foundations of hyperdimen- sional computing. arXiv preprint arXtv:2010.07426, 2020.
Tao Yu, Yichi Zhang, Zhiru Zhang, and Christopher De Sa. Understanding hyperdimensional com- puting for parallel single-pass learning. arXiv preprint arXiv:2202. 04805, 2022.
10

---

Under review as a conference paper at ICLR 2023
A APPENDIX
A.1 ABLATION STUDY
We show the full threshold study with dimensions varied from 8 to 1024:
Figure 6: Threshold Study
WAA WAY
W.w.A WT: 410
200 200 408
30 30
.00
100
sex
190 30 50 J00 200
A08 50x co
100 200
500 000
A.2 LEMMA AND PROOF
Lemma A.1
(01 (2) (.))))
arccos(
1 (1 2
10 10--22 110. 10.--111 -2112
Eg 1 1 20)=0)0
π
Proof. Consider the plane spanned by vector 01 O2 and 01 02 and the projection of x to this
plane, the two indicator function requires the angle < Px, 01 02 > and angle Px, 0, 02 >
to be smaller than I. Evaluating the expectation over X' is equivalent to evaluating the intersection
region of two semicireles. Therefore the result is m-arcros( (61 02) (8) 621
2n
Lemma A.2 When the coordinates of vector AO are ordered by absolute value: 1 |Agz 2 ... 2 |Ada. Then we have the following equality:
>
|A0|| >
AO
A
A
sup
sup ISiSA
A
|
A
AO
Proof. By the definition of the supremum, iterate over the list A [e1, C1 + c + +
... + ed), e; is the unit vector with the same sign as A0;, we know
AO Aه
Σ A0
sup AdE
2 sup
1
| 2
1
ISs5d
A
Now we show the < part. We show that when the A0's coordinates are ordered, the optimal A of the form
(sign(Ad)), (.0))....,igg(()))........ O....)) 0).
For any A with norm VJ.
A0. Ab < Σ AAA
11

---

Under review as a conference paper at ICLR 2023
Therefore,
AO A sup sup
AO Ad ||00| A01l2
Ei |ر0د| }.
sup 10,1-1,0,11
S sup
{
| |
15f5d
vīl|
Lemma A.3
(0, (8))
arccos
arccos(
V V (vi-vi--l)
10, 02112 16, -b2112
inf sup 01.02 0.
Proof. We will show the & part by construction. Set 01 (1, (1.v2-V1,....
vl,..., Vd
Vd - 1),02
(o,0...., 0). According to the Lemma A.2 and the monotonicity of arccos function, we have
(0: 02) (6, 62)
(01 (2) 02)
arccos(
arccos(
10, 10,-8211 82112 0211
0.-00 12 -
inf sup 01.02 01.02
sup 6,,02
01 01-02) 02)00,100-111 0z)
arccos(supp,
P 8, 02 |8 -22
π
arccos
EE (v5- - V--
π
Lemma A.4
(0) - 100 -821
arecos
arccos(
|00 0211 16, 6o
Vzj=i(V (V3 (V----1--
inf sup 0..02 01.02
2
π
arco0s
E (VT-v-TT
Proof. If there exists 87, 8 such that the LHS is smaller than monotonicity we know
by
11
(0) 0z) (0, - 02)
Co sup
Ca.
8,
10T
07 0 02
E (V5 v5-1)
Denote A0" 8 85. Without loss of generality, assume A E [0, 11 ||000 ||2 and
A > A0 2 AO%.
Starting from A Add we construct another feasible solution A Add without increas- ing the corresponding supremum value beyond Co. However, if we compare 20, 1....... A0, element- wisely with (vTe Te Vk C) < S d, the first A that not equal (VT: v 1)Co
greater than (vT Vl - 1)Co, this gives us the contradiction to the Co 's definition.
Also notice - = 1, Co < Ca. there always exists index k satisfying A > (Vi Vk: - 1)Co.
Assume the first 0; that is not equal to (vi - Vi- Vi-1)Co is still smaller than (Vi Vi - 1)Co.
By the above paragraph, we can find the first 0r, k > with 0 > (Vi: vk- - I)Co- Then we adjust (0;,07) O to ((Vi vi-T)Co. / (0:)2 + (0:)2 (Vi 1)=))) We verify that the assumed inequalities continue to hold. (There are cases for (07)2 +
12

---

Under review as a conference paper at ICLR 2023
(02)2 - - 1i-vii111 1) (Vi- - vk - 1) then just end this modification with (0:)² (VF - (vi v - T)Co) and then repeat the procedure.
(0))++
As the above procedure repeats, number # [A:02 (vh - / - T)Co) is strictly increased. When it stopped, the first non-(vk: vk 1 Co term is larger than the (vk /k I)Co and this gives us the contradiction.
Definition A.1 (Hadamard matrix) A Hadamard matrix is a square matrix with each entry being 1 or 1 and whose rows mutually orthogonal.
HHT = dld-
Theorem A.1 (Kainen & Krkova, 2020) The e-quasiorthogonal dimension of R
ddm [ S" x 5 d d=²//
A.3 WORKFLOW OF TRADITIONAL HDCS
Training
Inference
Training Data
Testing Data
Encader
Fnender
Majority Rule
Majority Rule
Hyper
Vector R
Similarty Check
Vector R
R
Vector R
Figure 7: Workflow of Traditional HDC.
where R indicates the binary final representation of each class c.
A.4 EXPLANATION OF THE LOW ACCURACY FOR EXPERIMENTS
(d S 64) IN NUMERICAL
As can be seen from Figure and Figure 5 the current Statement 3.1 and 3.2 do not predict the low accuracy for dimension I 64. This is caused by the breaking down the assumption that data can be embedded in d-dimensional linearly separable unit ball.
Consider a different setup in that the underlying dimension for data is fixed to be m. Each class is defined to be:
C = fo E B x. > 0, x.j+1), 15iSK.
Assume that the linear projection of data from m-diimensional linearly separable unit ball to d- dimensional (d < m) space in a coordinate-wise approach. It is equivalent to optimizing over the following hypervector set
Ooop....o0
0 E {0, (co,....,co. 0, = 0, i (col)....coo!),
Here 601; ..., 004 the coordinates index of the projected space.
13

---

Under review as a conference paper at ICLR 2023
The worst-case K-classes prediction accuracy of the m-dimensional data projected onto d- dimensional subspace
K Ex
Ace ==
inf 81. 01.02 Ax 100 col,..,,oa 8, 82. 8x 20
sup
sup
10 (60x>dra)
Accc m.,
The monotonicity comes from the fact that the two supremums are taken over monotonic hyper- vector set θ sequence.
When we randomly project the high-dimensional data into low-dimensional space, the accuracy of the majority rule suffers from two types of error, namely, misclassification and misrepresentation.
Here the misclassification error refers to the error from approximating d-dimensional linearly separable data while the misrepresentation error refers to the error caused by the difference between the projected distribution from the m--dimensional unit ball and a d-dimensional uniform distribution over the unit ball.
The misclassification error is characterized by the Statement 3.1 and 3.2 However, when the dimen- sion is small, the misrepresentation error can be much larger. This explains the left part (d < 64) of the curves in numerical experiments.
A.5 ADDITIONAL NUMERICAL RESULTS
Here we provide the numerical results when the weights in encoder is changed from floats to inte- gers. The results Table shows that performance does not degenerate when the integer weights are used in the encoder.
Table 2: Additional numerical results for integer encoder weights on MNIST.
Dimension
Accuracy
90.83%
32
95.12%
64
95.63 %
128
95.73%
14


Reviews:
[{"review_id": "eTEvHuo8Kpq", "reviewer": "Reviewer_5WTt", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper studied the factors affecting accuracy in HDC and proposed a more efficient HDC method. ", "summary_of_the_review": "Overall, I think this is an important study to make HDC more applicable, despite having some limitations. The paper would benefit from more clarify on the background. More benchmarks, even on some other simple datasets, could make it more convincing. ", "strength_and_weaknesses": "Strength:\n* The paper is mostly well organized and is straightforward to follow.\n* The study on dimension and accuracy looks very interesting. The result showing using much less dimensions looks very promising. I believe the technique proposed can be rather valuable especially for resource constrained hardware given the low dimension it can achieve.\nWeaknesses:\n* It would be helpful to provide more context on HDC basics, possibly some illustration figures to provide readers a more straight idea of how it works.\n* Is it possible to have some more benchmarks on some other datasets other than MNIST? I understand that the authors have stated that the method needs some simple dataset, having some other datasets, maybe some simple classification datasets would be more convincing.\n* Albeit having a better performance than existing methods, the performance on Cifar10 is not quite optimal from a application point of view. The author also states that HDC now mostly works on simple datasets.", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Ubc0YSPO5l", "reviewer": "Reviewer_781W", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 2, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a new hyperdimensional computing (HDC) methodology with low-dimensional hypervectors. The authors provide the theoretical results (for a binary classifier case) that the relatively lower dimensions can yield better performance. Furthermore, their theories suggest that the model performance asymptotically drops with respect to the hypervector dimension. Finally, the author empirically shows that their HDC method performs better than the existing methodology. ", "summary_of_the_review": "The authors provide theoretical and empirical results regarding the new hyperdimensional computing framework to accelerate the inference speed. However, overall the paper could be clearer to read and more self-explanatory. Mainly, I could not understand what methodology they used as their algorithm. The one big concern is that this HDC method works well on MNIST but not other datasets (CIFAR-10), which alerts my internal false alarm. Overall, I do not think the draft does not meet the ICLR bars.\n", "strength_and_weaknesses": "Strength\n\n1. A theoretical framework to explain the relationship between the hypervector dimensions and model performance.\n2. The author's empirical results are better than the existing methodology.\n\nWeakness\n1. Hard to read.\n2. Notations are not well defined. Mainly, I could not follow the idea in the Methods section. \n3. Figures are not self-explanatory. Hard to understand what idea is conveying.\n4. HDC method seems to only work on MNIST dataset. CIFAR-10 results are overall very poor. ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}, {"review_id": "JwP2q4fG47", "reviewer": "Reviewer_jTeX", "summary": "", "questions": "", "limitations": "", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper uses a neural network ($k$ binary neural network layers) as an encoder to derive binary features and then plug into hyperdimensional computing framework for inference. The paper manages to arrive at satisfactory performance on MNIST with a low dimension as 32, however, the connection from the motivation and analysis to the result is not clear to me. ", "summary_of_the_review": "Overall, it is still an interesting submission, currently I think it's under the bar of ICLR, unless some suggested experiments can be conducted to support the claims in the paper. ", "strength_and_weaknesses": "This paper examines the necessity for high dimension in HDC, however, the reasoning can not convince me in the following aspects:\n\n1. In standard HDC, hypervectors in the item memory is simply sampled from a high dimensional space, and the encoding process involves only binding and bundling, which are highly parallel and efficient operations. However, this paper extracts the hypervector for each data through training a binary neural network, thus the comparison in table 1 is not fair for some baselines which samples hypervectors, as the training/encoding cost is totally different, plus only inference complexity is given in table 1, not to say the retraining cost. \n\n-- 1.1 Further more, this method nearly abandons the advantage of HDC, using binary NN to derive hypervectors, why not just use a simple BNN? One can imagine, use an even complicated network to derive useful features as hypervectors, follows with the HDC framework, it would have same inference cost as the features are also binarized. Therefore, a comparison with the same BNN used should be included as a baseline to justify the improvement is not from training NNs. It's not surprising to me that this method can perform well in a low dimension. \n\n2. The author claims it's the orthogonality, not a high dimension, that is the determinant of HDC accuracy\n\n-- 2.1 if that holds true, a simple experiment is that, as shown in section 3.2, you can find $n$ strictly orthogonal hyper vectors in a low dimension $2^{\\lceil{\\log_2(n)}\\rceil}$ space by simply picking $n$ rows in the Hadamard matrix, then you can use the standard HDC encoding process for training, why suffer using a neural network to find hypervectors? Follow the author's logic, if this performs well, I would buy the claim, though I doubt it. \n-- 2.2 even with a trained BNN, did you test that the learnt low dimensional hypervectors are orthogonal to each other? I doubt it. \n-- 2.3 As the cited work Yu et al., 2022 shows, the orthogonality is not helpfully sometimes, but a related (with covariance) random sampled hypervectors help boost the HDC performance. \n-- 2.4 The analysis in section 3 looks interesting, however the conclusion holds only when the hypervectors are sampled uniformly from the ball, but not for general HDC, so is the claim that \"the lower the dimension, the higher the accuracy.\" to be conditioned, not for HDC. Though the result is still counter intuitive to me. \n-- 2.5 The high dimension brings not only orthogonality, but also robustness, i.e., the hypervector can be recovered even a large fraction of its element perturbed, this property would lost in a low dimensional space. \n\n3. After checking through the code, it looks to me the (MNIST) data to you BNN is floats? If not, how do you quantize the pixel values of images to binary? ", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "2: The contributions are only marginally significant or novel."}, "extra_text": {}}]

Author rebuttal:

Decision: Reject