PaperlayerView exact revision on arXiv

Source-linked AI summary

Classification using Hyperdimensional Computing: A Review

Lulu Ge, Keshab K. Parhi

arXiv:2004.11204v1cs.LGcs.AIcs.CLcs.NEeess.SP

TL;DR

HD computing addresses efficient classification with high-dimensional hypervectors by reviewing their representation, transformations, similarity measures, and accuracy-efficiency strategies. The review reports potential across letter, signal, and image data, especially for lightweight IoT classification, while noting acceptable rather than uniformly high accuracy.

  • Problem

    The paper examines how HD computing can support classification efficiently across diverse data types while balancing accuracy and resource use.

  • Method

    The paper reviews HD data representation, multiplication-addition-permutation transformations, similarity measurement, classification workflows, and strategies such as encoding, retraining, quantization, compression, and hardware acceleration.

  • Results

    Evaluations indicate strong potential for letter, signal, and image tasks, with reported gains including 17.2% average accuracy improvement for QuantHD and 69.7% model-size reduction for CompHD at maintained accuracy.

  • Takeaways & Limitations

    HD computing is a promising lightweight classifier for resource-limited IoT applications, with particular performance potential in tasks such as DNA sequencing.

Abstract

from arXiv · show

Hyperdimensional (HD) computing is built upon its unique data type referred to as hypervectors. The dimension of these hypervectors is typically in the range of tens of thousands. Proposed to solve cognitive tasks, HD computing aims at calculating similarity among its data. Data transformation is realized by three operations, including addition, multiplication and permutation. Its ultra-wide data representation introduces redundancy against noise. Since information is evenly distributed over every bit of the hypervectors, HD computing is inherently robust. Additionally, due to the nature of those three operations, HD computing leads to fast learning ability, high energy efficiency and acceptable accuracy in learning and classification tasks. This paper introduces the background of HD computing, and reviews the data representation, data transformation, and similarity measurement. The orthogonality in high dimensions presents opportunities for flexible computing. To balance the tradeoff between accuracy and efficiency, strategies include but are not limited to encoding, retraining, binarization and hardware acceleration. Evaluations indicate that HD computing shows great potential in addressing problems using data in the form of letters, signals and images. HD computing especially shows significant promise to replace machine learning algorithms as a light-weight classifier in the field of internet of things (IoTs).

I. INTRODUCTION

HD computing represents data as high-dimensional hypervectors and transforms them with simple operations for efficient classification. Its redundancy and orthogonality support robustness, while encoding remains important for accuracy.

  • Representation: HD computing represents cognitive-task data, including faces, language, speech, and images, as hypervectors with thousands of dimensions.Hypervectors may contain binary, integer, real, or complex components.
  • Motivation: Nearly orthogonal hypervectors distribute information broadly, contributing to robustness, scalability, energy efficiency, and shorter training and inference times.The paper attributes these features to ultra-wide representation and underlying mathematical operations.
  • Classification workflow: HD computing transforms data through multiplication, addition, and permutation, then compares test hypervectors with trained class hypervectors for classification.Class hypervectors are stored in associative memory, while test representations are generated during inference.
  • Limitations: HD classifiers are simpler and faster to train, but their accuracy is acceptable rather than comparable to traditional models because feature encoding is less understood.Encoding quality is identified as an important determinant of classification accuracy.
  • Tradeoff: Binary HD models are more hardware-friendly and efficient, whereas non-binary models generally achieve higher accuracy.This creates an accuracy-efficiency tradeoff in model design.

C. Similarity Measurement

HD computing measures similarity with metrics suited to binary or non-binary hypervectors and relies on high-dimensional orthogonality for dissimilar representations. Bundling combines inputs, while binding and permutation create associated or quasi-orthogonal vectors.

  • Similarity metrics: Cosine similarity is commonly used for non-binary hypervectors, while Hamming distance is used for binary hypervectors.Dot product and overlap are additional measures used in some HD variants.
  • Similarity metrics: Cosine similarity depends on vector orientation, with values near 1 indicating highly similar non-binary hypervectors.Orthogonal vectors have cosine similarity 0.
  • Similarity metrics: For binary hypervectors, normalized Hamming distance 0 indicates identical vectors, 0.5 indicates orthogonality, and 1 indicates diametrical opposition.The metric compares corresponding bit positions.
  • High-dimensional geometry: As dimensionality increases into the thousands, randomly generated hypervectors become increasingly orthogonal and therefore dissimilar.Operations on these orthogonal vectors can form associations or relations.
  • Data transformation: Bundling thresholds pointwise sums by majority rule, producing a binary hypervector that is maximally similar to its input hypervectors.Adding an even number of vectors can introduce a 0-or-1 bias, often reduced with an extra random vector.

2) Multiplication:

Multiplication binds two hypervectors through XOR, producing a representation that is approximately orthogonal to both operands. The reviewed distribution illustrates this dissimilarity for large binary hypervectors.

  • Multiplication: Pointwise multiplication, or binding, combines related hypervectors A and B as X = A⊕B to form an association.For binary hypervectors, the operation is implemented with XOR.
  • Multiplication: The bound hypervector X is approximately orthogonal to both A and B, making it dissimilar to each operand.This property supports representing associations without simply resembling the bound inputs.
  • Evaluation: Fig. 3 summarizes Hamming-distance distributions for X = A⊕B using 10,000-bit hypervectors across 3000 random cases.The figure evaluates the distance behavior of multiplication over large binary vectors.

3) Permutation:

HD computing uses hypervector operations to encode bindings, sets, records, and sequences, with permutation supporting sequence manipulation and reversible extraction.

  • Multiplication binds corresponding variable and value hypervectors to encode a pair such as “x = a”.
  • Addition combines bound pairs to represent sets and structured data records.A record can combine bindings such as (x = a), (y = b), and (z = c).
  • A value can be retrieved from an encoded record by binding the queried variable with the distributed record representation.
  • Permutation is used to encode and extend sequences, while inverse permutation supports recovering sequence elements.

III. LEARNING AND CLASSIFICATION BY HD COMPUTING

HD classification maps training and test data into hypervectors, trains class representations, and assigns each query the closest class label. The reviewed methodology supports multiple data types and encoding approaches.

  • HD classification began in the 1990s, with current applications described as a second wave.
  • During learning, an encoder maps training data into HD space and stores k trained class hypervectors in associative memory.
  • During inference, the encoded query is compared with every stored class hypervector, and the closest-distance label is returned.
  • HD computing can encode letters, signals, and images, using record-based and N-gram-based methods among its common approaches.

1) Record-based Encoding:

Record-based encoding represents feature positions and quantized feature values with hypervectors, combining them into a single encoded representation while preserving neighboring value correlations.

  • 1) Record-based Encoding: Record-based encoding uses separate hypervectors for feature positions and feature values.
  • 1) Record-based Encoding: Position hypervectors are mutually orthogonal, whereas neighboring level hypervectors are intentionally correlated.
  • 1) Record-based Encoding: Feature values are quantized into m levels, and each feature selects a corresponding level hypervector.
  • 1) Record-based Encoding: Continuous bit flipping generates successive level hypervectors, preserving neighbor correlations while making the first and last levels nearly orthogonal.
  • 1) Record-based Encoding: The N-gram-based alternative permutes level hypervectors by feature position before forming the final encoded hypervector.
  • 1) Record-based Encoding: For speech recognition, N-gram-based encoding achieves lower accuracy than the record-based counterpart.

C. Benchmarking Metrics in HD Computing

HD computing balances classification accuracy and efficiency through encoding, retraining, dimensionality reduction, binarization, sparsity, and hardware acceleration. Applications include language recognition, speech recognition, and nanotechnology-based implementations.

  • C. Benchmarking Metrics in HD Computing: Accuracy and efficiency are concurrent HD-computing objectives, motivating methods that improve either metric or both.
  • C. Benchmarking Metrics in HD Computing: Encoding choice affects accuracy across data types, while combining encoders can improve accuracy at the expense of hardware area.
  • C. Benchmarking Metrics in HD Computing: Iterative retraining improves training accuracy compared with single-pass training.
  • C. Benchmarking Metrics in HD Computing: Dimension reduction can save hardware resources while retaining classification accuracy within an acceptable range.
  • C. Benchmarking Metrics in HD Computing: Binarization accelerates computation and reduces hardware resources, while quantization degrades precision and QuantHD minimizes its accuracy impact.
  • 1) European Language Recognition Using HD Computing: The baseline encodes 26-letter trigrams in 19,683 dimensions but generalizes poorly as N-gram order increases, whereas 10,000-dimensional HD hypervectors generalize better.
  • 1) European Language Recognition Using HD Computing: The nanotechnology-based HD implementation reaches classification accuracy up to 98% across more than 20,000 sentences.

B. Signals

HD computing supports signal classification through hypervector encoding and similarity-based processing, with reported gains in speech recognition and seizure-detection energy efficiency.

  • Speech recognition: VoiceHD reached 88.4% recognition accuracy with M = 10 when N was fixed at 617.Recognition accuracy increased with M, while encoding efficiency degraded for M > 10.
  • Speech recognition: Combining VoiceHD with a three-layer neural network raised classification accuracy to 95.3%.VoiceHD+NN used 26, 50, and 26 neurons across its three layers.
  • Speech recognition: VoiceHD and VoiceHD+NN trained 4.6× and 2.9× faster than pure NN, while testing 5.3× and 4.0× faster, respectively.Pure NN classification accuracy was 93.6%.
  • Speech recognition: VoiceHD and VoiceHD+NN achieved 11.9× and 8.6× higher energy efficiency than pure NN, respectively.The comparison used pure NN as the reference model.
  • Seizure detection: Laelaps extracts local binary pattern codes from iEEG signals and uses HD computing to capture their electrode-wise statistics for seizure prediction.The processing chain encodes sampled iEEG signals and combines code and electrode hypervectors.
  • Seizure detection: Laelaps outperformed methods such as SVM in energy efficiency, while fair classifier-accuracy comparison with traditional methods remains future work.The review notes that simpler seizure detection and prediction algorithms also exist.

3) Quantization in HD Computing:

The review describes quantization, compression, and adaptive retraining as strategies for improving HD efficiency while preserving acceptable classification accuracy.

  • Quantization in HD Computing: QuantHD projects trained non-binary class hypervectors to binary or ternary models and uses retraining to compensate for quantization-related accuracy degradation.Similarity uses Hamming distance for binary models and dot product for ternary models.
  • Quantization in HD Computing: 17.2% average accuracy improvement was achieved by QuantHD over existing binarized HD computing at similar computation cost.The result applies to the comparison reported in the review.
  • Model compression: Reducing hypervector dimensionality improves efficiency and hardware-resource use, but experimental applications show an accuracy cost.The review frames accuracy and efficiency as a tradeoff when reducing model size.
  • Model compression: CompHD compresses class and query hypervectors into segments using orthogonal Hadamard-generated vectors to retain most original information.The method divides original hypervectors into s segments and uses projections in {−1, 1}^D.
  • Model compression: 69.7% average model-size reduction, 74% energy improvement, and 4.1× execution-time speedup were achieved at the original classification accuracy across three applications.The comparison used compression factor s = 20 and covered activity recognition, gesture recognition, and valve monitoring.
  • Adaptive training: AdaptHD addresses low accuracy and uncontrolled iterative-training duration through adaptive retraining followed by model binarization after convergence.Convergence is defined as less than 0.1% accuracy change across the last three retraining iterations.
  • Adaptive training: Hybrid AdaptHD combines iteration-dependent and data-dependent learning-rate adjustments to target both high accuracy and fast speedup.The adaptive schedule begins with a larger α and reduces it for fine-tuning as convergence occurs.
  • Adaptive training: Hybrid AdaptHD achieved 6.9× speedup and 6.3× energy-efficiency improvement compared with the existing HD algorithm.These are the evaluation results reported for the hybrid method.

6) A Binary Framework for HD Computing:

Binary HD frameworks trade some accuracy for hardware efficiency, while SemiHD extends HD classification to settings with limited labeled data and reports substantial gains.

  • Binary framework: Binary hypervectors generally provide lower accuracy but higher energy efficiency than non-binary hypervectors because they use Hamming distance instead of costly cosine similarity.Binary processing is more hardware-friendly than non-binary processing.
  • Binary framework: BinHD achieved 12.4× training energy efficiency and 6.3× training speedup over state-of-the-art HD computing with comparable classification accuracy.During inference, BinHD achieved 13.8× energy efficiency and 9.9× speedup.
  • Binary framework: During inference, BinHD achieved 13.8× energy efficiency and 9.9× speedup over state-of-the-art HD computing with comparable classification accuracy.The evaluation covered four practical applications.
  • Semi-supervised learning: SemiHD performs self-training with a small labeled set and a large unlabeled set by iteratively adding high-confidence pseudo-labeled data.The framework encodes data in 10,000-dimensional HD space and stops when accuracy changes by no more than 0.1%.
  • Semi-supervised learning: SemiHD improved supervised HD classification by 10.2% on average.Its FPGA implementation was also reported as 7.11× faster and 12.6× more energy efficient than the best CPU implementation.

8) HD Computing for Unsupervised Learning:

HD computing supports classification across signals, letters, and images after encoding data into hypervectors, while ongoing work targets accuracy, efficiency, and broader cognitive capabilities.

  • Applications: Character-recognition evaluations report good performance and robustness against noise.A 4,000-bit system matched the average accuracy of a 12,000-bit system at 0% distortion and reached 89.94% average accuracy at 14.29% distortion.
  • Applications: HD computing shows potential for signals, letters, and images when these data are transformed into the HD space.Pre-processing may include feature extraction and encoding.
  • Efficiency and accuracy: HD computing can combine quantization with binarization to improve efficiency while minimizing accuracy loss.The review also identifies compression, retraining, non-binary models, and hardware acceleration as improvement strategies.
  • Future directions: HD computing remains in its infancy, with further exploration needed beyond classification toward analogical reasoning, semantic generalization, and relational representation.The review frames these as additional cognitive tasks for future study.
  • Future directions: Future work should develop hardware-friendly similarity metrics that can improve accuracy beyond widely used cosine similarity and Hamming distance.The review also identifies multiple class hypervectors and hybrid systems as open research directions.
  • Efficiency and accuracy: Hardware implementations may improve speed and energy efficiency, while sparse representations can reduce memory footprints depending on the application scenario.The review notes that dense-versus-sparse choices should be matched to application requirements.

V. CONCLUSION

The review summarizes HD computing’s operations, capabilities, applications, and improvement strategies. It concludes that HD computing can serve as a lightweight classifier, but suitability depends on the accuracy–efficiency tradeoff.

  • Conclusion: HD computing may achieve high robustness, fast learning, hardware-friendly implementation, and energy efficiency.The conclusion presents these as potential properties of the model.
  • Conclusion: HD computing shows potential as a lightweight classifier for applications with limited resources, including seizure, speech, character, and language tasks.The conclusion also reports outstanding classification performance for certain problems such as DNA sequencing.
  • Conclusion: Users should evaluate HD computing’s suitability for each application because it can provide outstanding accuracy in some cases but acceptable accuracy with high efficiency in others.The conclusion identifies balancing accuracy and efficiency as an important research area.
Loading 2004.11204v1…