This tutorial provides an introduction to a class of approaches to address symbolic computational problems using vector calculations. They work in vector spaces with thousands of dimensions and are referred to as Vector Symbolic Architectures (VSA), high- (or hyper-) dimensional computing, or hypervector computing (to emphasize the really large number of dimensions). They are particularly interesting if the task at hand already includes high-dimensional representations (e.g., from deep neural networks), if we want to perform symbolic computations with subsymbolic entities, or if we need a high fault-tolerance in the representations or in the operations. High dimensional vector spaces have special and sometimes counter intuitive properties. A well-known example is the curse of dimensionality: the effect that some algorithms that work well in low dimensional spaces, fail in higher dimensional spaces.

However, there are further effects of high dimensionality, that can be exploited;  for example, random high-dimensional vectors are very likely almost orthogonal. This and other properties are used in carefully designed vector operations of VSAs. Symbols are encoded in very large vectors, much larger than would be required to just distinguish the symbols. VSAs use the additional space to introduce redundancy in the representations, usually combined with distributing information across many dimensions of the vector (e.g., there is no single bit that represents a particular property - hence a single error on this bit can not alter this property). Very importantly, measuring the distance between vectors allows to evaluate a fuzzy relation between the corresponding symbols. The operations in VSAs are mathematical operations that create, process and preserve the fuzziness of the representations in a systematic and useful way. For instance, an addition-like operator can overlay vectors and creates a representation that is similar to the overlaid vectors.

VSAs build on seminal works by Smolensky [1], Plate [2], and Kanerva [3]. The underlying high-dimensional distributed representations share properties with representations from biology and are used in several computational models of aspects of brains, e.g. [4,5]. There is a variety of available VSA implementations (e.g., see [6] for an overview) and a large number of applications (e.g., model superposition in neural networks [7], approximate inference [8], analogical reasoning [9], NLP [10], long-short term memory [11], robotics [12], …).

This tutorial will present this class of approaches to an interested audience with little or no prior knowledge of this topic. We will outline the underlying mathematical properties of high-dimensional vector spaces that are exploited in VSAs. There are several different VSA implementations available which differ in the underlying vector spaces (e.g., binary, real, or complex numbers, sparse or dense vectors) and the design of the operations (with potentially large effect on their properties). We will provide an overview of existing architectures and demonstrate their strengths and weaknesses based on a set of practical experiments. We will outline existing applications and present our own experiences on using VSAs in combination with real world sensor data in the area of mobile robotics, e.g., combinations with deep learning visual front-ends for recognizing places from images of a 2800 km trip through Norway across different seasons.

[1] Smolensky, P. (1990) Tensor product variable binding and the representation of symbolic structures in connectionist systems. Artificial Intelligence 46(1–2):159–216

[2] Kanerva, P. (2009): Hyperdimensional computing: An introduction to computing in distributed representation with high-dimensional random vectors. Cognitive Computation 1(2), 139–159

[3] Plate TA (1994) Distributed representations and nested compositional structure. Ph.D. thesis, Toronto, Ont., Canada, Canada

[4] Hawkins, J., Ahmad, S.: Why neurons have thousands of synapses, a theory of sequence memory in neocortex. Frontiers in Neural Circuits 10, 23 (2016). DOI 10.3389/fncir.2016.00023

[5] Eliasmith C, Stewart TC, Choo X, Bekolay T, DeWolf T, Tang Y, Rasmussen D (2012) A large-scale model of the functioning brain. Science 338(6111):1202–1205.

[6] Schlegel, K., Neubert, P., Protzel, P. (2020) A comparison of Vector Symbolic Architectures. CoRR, abs/2001.11797

[7] Cheung, B.,Terekhov, A., Chen, Y., Agrawal, P., Olshausen, B. (2019) Superposition of many models into one. NeurIPS

[8] Widdows, D., Cohen, T.: Reasoning with vectors: A continuous model for fast robust inference. Logic journal of the IGPL / Interest Group in Pure and Applied Logics (2), 141173 (2015)

[9] Kanerva, P.: Computing with 10,000-bit words. In: 2014 52nd Annual Allerton Conference on Communication, Control, and Computing (Allerton), pp. 304–310 (2014). DOI 10.1109/ALLERTON.2014.7028470

[10] Gayler, R.W.: Vector symbolic architectures answer jackendoff’s challenges for cognitive neuroscience. In: Proc. of ICCS/ASCS Int. Conf. on Cognitive Science, pp. 133–138. Sydney, Australia (2003)

[11] Danihelka I, Wayne G, Uria B, Kalchbrenner N, Graves A (2016) Associative long short-term memory. In: Balcan MF, Weinberger KQ (eds) Proceedings of the 33rd international conference on machine learning, proceedings of machine learning research, 48. PMLR, New York, pp 1986–1994.

[12] Neubert, P., Schubert, S., Protzel, P. (2019). A neurologically inspired sequence processing model for mobile robot place recognition. IEEE Robotics and Automation Letters and International Conference on Intelligent Robots and Systems (IROS)