IEEE Circuits and Systems Magazine - Q2 2020 - 35

A. The HD Classification Methodology
A system diagram for the classification tasks using HD
computing is shown in Fig. 5. In general, 1). during the
learning phase, the encoder employs randomly generated hypervectors (pre-stored in the item memory) to
map the training data into HD space. A total of k class
hypervectors are trained and stored in the associative
memory. 2). During the inference phase, the encoder
generates the query hypervector for each test data.
Then the similarity check is conducted in the associative memory between the query hypervector and every
pre-trained class hypervector. Finally, the label with the
closest distance is returned.
B Encoding Methods for HD Computing
HD computing can address various types of input data,
including letters, signals and images. However, we need
to map those input data into hypervectors, and this process corresponds to encoding. The encoding process is
somewhat similar to extraction of features. Among the
existing HD algorithms, the two encoding methods commonly used include record-based encoding and N-grambased encoding. A toy example related speech signals is
used for illustration.
Using Mel-frequency cepstral coefficients (MFCCs)
[22], the voice information stored in continuous signals
can be mapped into the frequency domain. A feature
vector with N elements can be obtained. Each element
has its feature value, which is evenly discretized or
quantized from {Fmin, Fmax} to m different levels.
1) Record-based Encoding
This encoding method employs two types of hypervectors, representing the feature position and feature value,
respectively. It may be noted that a variation of recordbased encoding based on permutations and a chain of
binding operations was proposed in [24]. In this encoding, position hypervectors ID i are randomly generated
to encode the feature position information in a feature
vector, where 1 # i # N. . The feature value information
is quantized to m level hypervectors {L 1, L 2, f, L m}. For
an N-dimensional feature, a total of N level hypervectors
Lr i should be generated, which are chosen from m level
hypervectors {L 1, L 2, f, L m} based on the feature value.
Note that, position hypervectors ID i are orthogonal to
each other, while level hypervectors {L 1, L 2, f, L m} are
supposed to have correlations between the neighbors.
To realize this, in [25] the first level hypervector L 1
SECOND QUARTER 2020

r-epresents the feature value Fmin . Then each time, d/m
randomly selected bits are flipped to generate the next
level hypervector, where d is the dimensionality of the
hypervectors. The continuous bit-flipping was first introduced in [23] and later followed by other use cases [26]-
[28]. This bit-flipping approach ensures the correlations
between neighbor levels, while the last level hypervector
L m is nearly orthogonal to L 1 . The encoding occurs by
binding each position hypervector with its level hypervector. As described in Eq. (15), the final encoding hypervector H can be obtained by adding these results together. The entire encoding process is illustrated in Fig. 6.
H = Lr 1 5 ID 1 + Lr 2 5 ID 2 + f + Lr N 5 ID N ,

Lr i ! {L 1, L 2, f, L m}, where 1 # i # N.

(15)

2) N-gram-based Encoding
The method of mapping N-gram statistics into hypervectors was proposed in [30]. First random level hypervectors are generated. Then the feature values are

Associative Memory
Class 1 Vector
Training
Data

Encoder

Class 2 Vector
Class k Vector

Minimum
Distance

III. Learning and Classification by HD Computing
The first wave of using HD for classification started in
1990s [17]-[20]. The current applications of HD for classification can be interpreted as the second wave.

Similarity Check
Encoder

Test Data

Query Vector

Figure 5. Classification overview with HD computing [21].

Fmax

1
Fmin
iM
ID1

CiM
L1

iM
ID2

CiM
L2

iM
IDN

CiM
LN

H
Figure 6. Record-based encoding [23]. Note iM refers to item
memory, which stores the position hypervectors, and CiM
refers to continuous item memory [13], which stores level
-hypervectors.

IEEE CIRCUITS AND SYSTEMS MAGAZINE

IEEE Circuits and Systems Magazine - Q2 2020

Table of Contents for the Digital Edition of IEEE Circuits and Systems Magazine - Q2 2020