Understanding Hyperdimensional Computing for Parallel Single-Pass Learning
This work addresses accuracy limitations in HDC, an energy-efficient learning paradigm, for applications in low-power hardware, representing a significant but incremental advance.
The paper tackled the problem of low model accuracy in hyperdimensional computing (HDC) by analyzing its theoretical limits and proposing new methods, including random Fourier features and finite group vector symbolic architectures, which improved state-of-the-art HDC accuracy by up to 7.6% while maintaining hardware efficiency.
Hyperdimensional computing (HDC) is an emerging learning paradigm that computes with high dimensional binary vectors. It is attractive because of its energy efficiency and low latency, especially on emerging hardware -- 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.