Capacity Analysis of Vector Symbolic Architectures

Hyperdimensional computing (HDC) is a biologically-inspired framework which represents symbols with high-dimensional vectors, and uses vector operations to manipulate them. The ensemble of a particular vector space and a prescribed set of vector operations (e.g., addition-like for “bundling” and outer-product-like for “binding”), as targeted to HDC, forms a vector symbolic architecture (VSA). While VSAs have been employed in numerous learning applications and have been studied empirically, many theoretical questions about VSAs remain open. In this paper, we analyze the representation capacities of four common VSAs: MAP-I (vectors take integer values), MAP-B (binary vectors and operations), and two VSAs based on sparse binary vectors. “Representation capacity” here refers to bounds on the dimensions of the VSA vectors required to perform certain symbolic tasks, such as testing for set membership and estimating set intersection sizes for two sets of symbols, to a given degree of accuracy. We also propose a novel variant of a Hopfield network (a simple model of associative memory), and analyze its ability to perform some of the same tasks that are typically asked of VSAs. Our analyses establish and leverage connections between VSAs, matrix sketching algorithms, and Bloom filters. In particular, some of our analyses amount to showing that certain random projections with less than full randomness have length-preserving properties, and we give novel analyses of Bloom filters and Counting Bloom filters, with regard to rapid estimation of the size of set intersections.