The blessing of dimensionality

1.Introduction and motivations

Artificial neural networks (ANNs) have been instrumental in the development of numerous successful deep-learning applications. Nevertheless, the increasing complexity of these systems has given rise to a number of challenges. It is extremely difficult to map their internal operations to the cognitive mechanisms that regulate reasoning and learning in the human brain, particularly in terms of the underlying representation of objects, their abstractions, and the relationships between them. Consequently, the transparency of the decisions made is hindered by the difficulty in their interpretation and justification [42]. Furthermore, the considerable and continuously increasing computational resources required to operate these systems have become a significant concern for sustainability [54,65].

The limitations of sub-symbolic approaches have long been patent. For example, considering an ANN trained to recognize objects of different shapes may use neurons in its output layer, each indicating a different shape. To make the ANN also discern the color of an object many more output neurons would be needed: one per combination of shape and color. However, it seems unlikely that human brains are organized to have one neuron per combination. Instead, neuroscientists argue that information in the brain is represented by the simultaneous activity of numerous (thousands of) neurons and the same set of neurons could represent entirely different concepts [7,26].

The 90s saw the emergence of cognitive models [26,52] that depend on very high dimensionality and randomness. A framework called Vector Symbolic Architectures (VSAs) [9] is essentially a family of theories for cognitive representation that provide operations for building data structures based on high-dimensional vectors [51] and, in combination with neural networks, trace a path toward symbolic computation systems that are able to learn from data. In hyperdimensional computing11 (HDC) [26,28] each piece of information is represented as a hyperdimensional vector, or hypervector, i.e., a large array of numbers, representing a point in high-dimensional space. These mathematical objects and the algebra to manipulate them are flexible and powerful enough to address the mentioned limitations fostering a new approach to Artificial Intelligence (AI): a new approach in which efficient and robust computing can make decisions that are more transparent. HDC/VSA originated from proposals of integrating the advantages of the symbolic approach to AI, such as compositionality and systematicity, and those of the ANNs to AI (connectionism), such as vector-based representations, learning, and grounding (see [31,32] for a recent comprehensive survey).

Vectors are used to represent both features (variables) and also the values that can be assigned to the variables. The vectors must be distinct. This distinctness can be quantified by their orthogonality: in a hyperdimensional space, there is a huge number of such mutually orthogonal vectors. But if consider also vectors that are nearly orthogonal, the number of such distinct hypervectors explodes: millions of nearly orthogonal hypervectors in a 104-dimensional space. Because there are so many possible nearly orthogonal vectors in such a space, one can just represent the mentioned items with distinct random vectors which are almost guaranteed to be nearly orthogonal.

Given hypervectors for features and values, systems have been conceived to manipulate them using basic operations which correspond to ways of symbolically manipulating entities/concepts and allow to build a structured representation. Formal algebras of hypervectors have been devised based on such operations thus allowing for symbolic reasoning on the resulting representation models [28,31].

An advantage of the representation is the tolerance to errors: even if a hypervector suffers significant numbers of random bit flips, it is still close to the original vector. Thus reasoning using these vectors is not meaningfully impacted in the face of errors. Another advantage of the approach is transparency: the algebra clearly tells why the system chose a given answer. This opens the way to analogical reasoning, which is expected of any AI system.

HDC seems also well suited for a new generation of low-power hardware and it is compatible with in-memory computing, that is performed on the same hardware that stores data unlike standard architectures that inefficiently transfer data back and forth between memory and CPU. Some of these new devices can be analog, operating at very low voltages, making them energy-efficient but also prone to random noise. As such this solution is gaining interest in the context of Internet of Things and edge computing [65].

Several applications of HDC/VSA have been proposed in the last decade (see [32] for a comprehensive survey). Specific algorithms for such representations have been developed to replicate typical tasks for (deep) neural models such as image classification. The strength of hyperdimensional computing lies in the ability to compose and decompose hypervectors for reasoning. This strength has been recently demonstrated [17] on the solution of a classic abstract visual reasoning problem, known as Raven’s progressive matrices, that results particularly challenging both for ANNs and even for humans (it has been used in IQ tests).

Complex structures, such as those in images, scenes, episodes, can be represented as single hypervectors that contain information about all the objects involved, including their properties. Basically, an algorithm analyzes the features of each instance using some predetermined scheme and creates a hypervector for each image. Then, for each class it can aggregate via simple operators (e.g., addition) the hypervectors for all instances of the class to create a hypervector which can be stored in memory. Given a new unlabeled case, a hypervector is created for it and then compared against the stored class hypervectors to determine by analogy the most similar class. Our idea is to adopt this representation for AI methods dealing with more abstract objects such as individuals and their relations within Knowledge Graphs (KGs) [19], as well as related schema-level knowledge, such as classes and properties.

In the rest of the paper, the basics of neural representations and their properties are recalled in §2 while the distributed representation used for vector-space architectures is illustrated in §3. A simple HD model is presented in §4 to show how complex structures can be built from atomic symbols (hypervectors). Then, in §5 and §6, we examine the application of analogical reasoning and learning approaches, respectively, outlining possible extensions, with a particular focus on KGs. Finally, §7 concludes the paper and delineates further potential research.

2.Neural representations and their properties

Symbolic representations [46] are natural for humans and widely used in AI: each object is represented by a symbol (by objects we refer to items of various nature and complexity, such as physical objects, features, relations, classes, and so on). More complex representations can be composed from simpler ones and they naturally possess a combinatorial structure that allows producing indefinitely many symbolic expressions by means of rules / programs (natural language can be considered as example of such representations). Symbols are characterized by an explicit 0/1 similarity: the same symbols have maximal similarity, whereas different symbols have null similarity and are, therefore, called dissimilar. Comparing composite symbolic structures requires to follow edges and/or match vertices of underlying graphs to reveal the whole structures and calculate the similarities. Hence, scalability problems arise in similarity search and reasoning with models when they require complex sequential operations.

Two main types of connectionist representations are distinguished: localized and distributed [59]. Localized representations are similar to symbolic representations as for each object there exists a single corresponding element in the representation (e.g., a single neuron / node or a single vector component). Connections between elements can be created to link localized representations, corresponding to pointers in symbolic representations. However, constructing structures that include combinations of object representatives may require the allocation of a potentially infinite number of new additional elements / connections, which is neuro-biologically questionable. Also, similarly to symbolic representations, localized representations lack a sufficient semantic basis, namely an immediate and explicit similarity between the representations. Different neurons representing different objects are dissimilar and estimating object similarity requires additional computation.

Distributed representations [18,51] were inspired by the concept of holographic representation which is an alternative connectionist model of the brain in which information is distributed across many neurons. In distributed representations, the state of a finite set of neurons is modeled as a vector where each vector component represents a state of the particular neuron. They are defined as vector representations, where each object is represented by a subset of vector components, and each vector component can be part of the representations of many objects. This regards representations of objects of various complexity, from elementary features or atomic objects to complex scenes/objects that are represented by (hierarchical) compositional structures. The state of individual components of the representation cannot be interpreted without knowing the states of other components. Hence the semantics of individual components usually cannot be defined in isolation. However, for engineering applications and cognitive modeling, distributed representations of similar objects should be similar according to some similarity measure over the vector space. As pointed out in [31], distributed representations should endowed with some desirable properties:

Conventional implementations of brain-like symbolic computations also require reliable hardware [61], since any error might result in a fatal fault [31]. Neural representations are subject to various context effects, as evident from the kinds of errors we make, as they are not optimized for fast and reliable arithmetic operations. The context effects likely reflect a compromise in favor of vital functions of the brains [26,28].

Computers adopt a binary representation: an individual circuit component has two possible states, as electronic components are most reliable when they are bistable. The representation must discriminate. The binary patterns for different things must be different. However the choice of the patterns is often a compromise aimed at performing efficient operations on them (e.g., the positional representation for numbers). Neural representations are carried on components that are nonbinary. Yet many context effects can be demonstrated with binary patterns and operations. The important properties of the representation descend from high dimensionality rather than from the nature of the single dimensions. In contrast to dimensionality reduction, a standard practice in the processing of high-dimensional data, a very high dimensionality can actually facilitate processing: “instead of being a curse, high dimensionality can be a blessing” [26]:

3.Hyperdimensional representation models

Hyperdimensional representation spaces are primarily characterized by the domain of the vector components (e.g., binary, real, or complex numbers) and by their dimensionality, which determines the set of atomic hypervectors. They are also characterized by their sparseness, given a probability distribution which defines a space of hypervectors with independent components drawn from this distribution. Actually, different representation spaces can coexist in a cognitive system. For example, considering a typical representation space of 104-bit patterns contains a total of 2104 hypervectors (points). The space essentially comprises all the corners of a 104-dimensional unit (hyper)cube, yet an infinitesimal fraction of them would be required to represent meaningful entities.

Basic operations It was shown [26,28] that it is possible to encode and decode all data structures typical of ordinary computing, such as sets, sequences, lists, and further extensions, in terms of basic operations on holographic vectors, namely, superposition and binding. The former is used to form an hypervector that represents several others (in analogy to simultaneous activation of neural patterns). The latter is used to associate two (or more) hypervectors that should be bound together (e.g., a variable and its value).

Considering the operations22 on vectors of real numbers, which are commonly used in the ANNs research, these basic operations33 can be defined in terms of:

Further related operations are: weighting with a constant, aX, where each component of the vector X is multiplied with the same number a, and the result is a vector; subtraction (difference) which is accomplished by adding to the first the second vector’s complement, that is obtained by multiplying each component by −1 (or just flipping the bits in case of binary vectors); two vectors can be multiplied to give their so-called inner product, that can be used as a measure of similarity (e.g., the cosine); their outer product, which yields matrices, is a form of multiplication that is employed extensively for fitting the weights of ANNs. Multiplying a vector by a matrix, which is another common operation with ANNs, results in a vector that may require normalization.

The choices of the representation for the atomic symbols and of the implementation of the basic operations determine also the definition of a measure of similarity on the hyperdimensional space for the comparison of hypervectors. Examples of such measures are: dot-product, cosine, Pearson’s correlation, and the Hamming distance [28,31].

For example, considering a space of binary hypervectors, their similarity can be measured by the Hamming distance, which amounts to counting the number of bits that differ. Then the maximum distance is 104 and this measure can be expressed as relative to the number of dimensions. The (binomial) distribution of the distances makes them as highly concentrated halfway around 5000-bits, the mean, with a standard deviation of 50. Thus, a sphere of limited radius (say, 550-bits) centered at the mean distance will contain most of the space. If we consider two arbitrary random hypervectors, they are likely to differ by about 5000 bits and the same would hold also for each in a sequence of randomly chosen hypervectors for the representation. This makes them unrelated and the representation robust, since a very large number of bits in a noisy vector must change (more than 1/3) to make it unrelated to the original. From the opposite perspective, we can consider the relation of similarity between vectors, which remains strong until their distance approaches 0.5 (i.e., 5000-bits): the neighborhood volume within 3333-bits is quite limited with respect to the total space while unrelated vectors abound after a distance approaching 0.5. The neighborhoods of any two unrelated vectors have points in common: points that turn out to be very similar to any two unrelated points. Vectors can be related by transformation, i.e., by the way one is transformed into another or by the combination of several vectors in a new one.

4.A structured knowledge representation model

Given a content-addressable memory for hypervectors, and hyperdimensional arithmetic, a representation model for entities of various kinds can be devised. Models are based on the representation of atomic entities and on hypervector transformations defined in terms of the basic operations introduced above.

For illustrative purposes we will refer to simple models based on binary hypervectors with related operators and similarity measures. An extensive detailed presentation of the HDC/VSA models can be found in [31] (§2.3).

Item memory An ideal architecture with a very large number of addresses would require storage for a huge number of locations. A pattern (a hypervector) X may be stored in a location addressed with a pattern A (or any A′ similar to A). This solution is called heteroassociative, as opposed to the autoassociative memory where each X is stored in such a way that X itself is used as its address (content addressable memory), which makes retrieval much easier. A pattern becomes meaningful when it is selected to represent an entity. For later reference, they are stored in an autoassociative memory that forms a catalog of meaningful patterns that can be recognized even in the presence of noise. When searching with a noisy pattern, the corresponding noise-free stored pattern is retrieved (hence the name clean-up memory) in a kind of nearest neighbor search among the stored patterns. Arithmetic operations on patterns produce approximate (noisy) results that require cleaning up to recover the original pattern. Some operations produce meaningful patterns that are very similar to each other making them difficult to retrieve. For example, the sum pattern S=A+B is similar to both A and B. Therefore, it is advantageous to transform S prior to its storage, mapping it into a different region of space, provided that the transformation is invertible.

Symbols for basic entities A formal system can be built up from a set of basic atomic entities. The smallest meaningful unit of the cognitive code is a hypervector. The atomic entities, or individuals, are thus represented by random points of the hyperspace. To represent something new that does not consist of entities already represented in the system, one can simply randomly draw a new vector that must be stored in item memory for later reference. The new vector will be unrelated to all the vectors in memory (its distance from all of them is very close to 0.5), i.e., it will be approximately orthogonal to each of them. For example, a 104-dimensional space has 104 orthogonal vectors and a huge number of nearly orthogonal vectors [26].

Sets and superposition Both the set and its elements can be represented using hypervectors. The simplest commutative operation (such that the order does not matter) is vector addition. A sum-vector (or a the mean-vector) has the property of being similar to the added vectors. Thus, the elements are said to be visible in the representation of the set, and sets that share elements are represented by similar vectors. To distinguish the sum-vector representing the set from the vectors of its elements, it must to be mapped into a different region prior to its storage in memory. The mapping should be invertible so that the original sum-vector can be retrieved, and it should preserve distances so that the memory can be searched even with partial or noisy sums. Elements are recovered from a stored sum-vector by first restoring the sum (with the inverse mapping) and then searching the memory for the best match with it. The other elements can be retrieved from the difference-vector resulting from subtracting the former [26]. Large sets can be better analyzed by accumulating (partial) sums from the vectors recovered and by subtracting them from the original sum to get the various elements. However, if the unmapped sum has been stored in the item memory, this method fails. It is also possible to find previously stored sets (i.e., sums) that contain a specific element by searching the memory with that element (with its vector). Yet, preliminarily, the element must be mapped into the same part of space, i.e., via the same mapping, used before storing sum-vectors. Also a multiset (a bag) can be represented as the sum of their elements, which can be extracted from the sum in the same way.

Multiplications and related mappings Without loss of generality, two simple forms of mapping will be recalled for hyperspaces of (0,1)-binary vectors (or also in (1,−1)-binary bipolar form) [26]. The first is the multiplication of vectors that will be denoted with A∗B. In a bipolar binary system ordinary multiplication can be used. In the case of binary vectors can be defined as the component-wise eXclusive-OR, XOR (e.g., 1010...01XOR1001...11=0011...10). This can also be thought of as a special case of Euclidean distance or a sum modulo 2, often indicated with ⊕. XOR is commutative and each A is its own product-inverse since A∗A=O, where O is the vector with all 0s and it is the unit element, as A∗O=A. It is easy to see that the Hamming distance between two vectors is simply the number of 1s in their product, denoted d(A,B)=|A∗B|, where |·| represents the count. This distance is usually expressed relative to the number of dimensions. Multiplication can be thought of as a mapping: multiplying X by A maps it to the vector XA=X∗A which is as far away from X as there are 1s in A (i.e., d(XA,X)=|A|). A typical random vector A has about half of its bits set, so XA is in the part of the space that is unrelated to X in terms of the distance criterion. This shows that multiplication randomizes. Moreover, it is also distance-preserving:

Therefore, when a set of points is mapped via multiplication by the same vector, the relative distances are maintained (the cluster of points is just moved to a different part of space). High-level cognitive functions (e.g., analogy) can be defined in terms of these mappings where the relations between entities are more important than the entities themselves. In the previous example, A can be regarded as a specific mapping applied to vectors X and Y. The same argument applies if we consider two mappings A and B and examine their effect on the same vector X: X would be mapped onto XA and XB that are as far apart as A and B. Therefore, similar vectors lead to similar mappings. Similar mappings map a vector to similar vectors.

Permutation is another form of multiplication that reorders the vector components. The permutation of a vector A can be denoted either as the application of a function, ρ(A), or as a multiplication by the corresponding permutation matrix, ΠA. Alternatively, it can be described as a list of integers (positions) in the permuted order. As a mapping, it has desirable properties: it is invertible, it distributes over addition (and over XOR multiplications) and the result is dissimilar to the vector being permuted. Moreover, distances are preserved:

A random permutation is one where the order is chosen randomly from the n! possible permutations, where n is the dimensionality of the hypervectors. Given random permutations ρ1 and ρ2, it can be shown [26] that they agree on the average in only one position, thus the distance between ρ1(A) and ρ2(A) is about 0.5, so they map A to different parts of the space.

Associations: Pairs and bindings A pair is a basic unit of association in which two elements A and B correspond to each other. They can be represented with a multiplication: C=A∗B. Knowing C and one of its elements, one can find the other by multiplying C with the inverse of the known element. With XOR, any pair of two identical vectors will be represented by the 0-vector O. This can be avoided adopting a slightly different multiplication that neither commutes nor is a self-inverse. One can encode the order of the operands by permuting one of them before combining them. By permuting the first, we get: C=A∗B=ρ(A)XORB. This kind of multiplication has all the desirable properties mentioned above. However it is not associative because of the permutation, i.e.: ∀A,B,C:(A∗B)∗C≠A∗(B∗C). In a holistic representation, a binding can be represented as a multiplication of the variable vector X by the value vector A: X∗A. The unbinding requires a simple multiplication by one of the two elements to get the other.

Records as sets of bound pairs A complex individual can be represented as a record consisting of fields that are variables, roles in Description Logics (DLs) [1], each of which stands for a relationship to a value or to another individual. In a holistic representation, roles are explicitly represented as vectors. Vectors for unrelated roles, such as name and address, can be chosen at random. A role bound to its filler is represented by the product X∗A defined as shown above. A single entity can be defined with a record that combines multiple role–filler pairs:

A record-vector is self-contained as or it includes role-filler pairs explicitly. Moreover, it will be similar to all of its pairs, while it will be dissimilar to the single role and filler vectors because of the products. Unbinding can be used to extract the contained information:

Adding more pairs (products) to a record-vector E, gives us a new sum-vector E′ that is very similar to E because it shares four pairs with it. One might be interested in querying the whole database of records for some property or in processing some of its records. For example, knowing a filler of one of the roles in one record (the role is not known) can enable one to get the filler of that role in another record. Together with standard database operations, different type of computing become possible: they are known as holistic mappings or transformation without decompositions [32] that can be used to resolve proportional analogies (see §5).

Graphs A graph G consists of a set of nodes connected by arcs (or edges). Arcs can either be undirected or directed. In a simple transformation of graphs into hypervectors [10,31] a random vector is assigned to each node of the graph and an arc is represented as the binding of vectors of the nodes it connects, e.g., the edge between nodes A and B is A∗B. The whole graph is represented simply as the superposition of hypervectors representing all edges in the graph.

To represent directed graphs, the directions of the edges should be included into their vectors. This can be done by applying a permutation, so that the directed edge e.g., one from A to C, is represented as A∗ρ(C).

This example and more complex graphs that represent scenes or episodes can be found in [31], §3.5.2.

5.Reasoning by analogy

Reasoning by analogy depends on specific human capacities: the facility for conceptual abstraction and the flexible recombination of atomic components to describe new unseen situations.

Proportional analogy problems Prior work has targeted so-called proportional analogy problems and leveraged large networks with relatively little structure to map an inferred relation between two entities onto a third one. These problems are described in the form: A:B::C:?, to be read A is to B as C is to ?, where A and B represent two entities between which a relation is computed and C is an entity onto which this relation is applied to produce the solution (another unknown entity). Typical such problems are related to the domain of images, visual analogy problems, tackled in several works (e.g., see [56]).

Computing such a relation in hyperdimensional representations is extremely simple, namely it suffices to subtract B from A. This lacks a full appreciation of the nature of analogy, namely the substitution of atomic components that may be embedded in larger data structures. This computation is not well-captured by the mere subtraction. However, in a HDC/VSA framework, substitution of atomic components within/between complex data structures can be both elegant and very efficient if the data structures are constructed by means of binding. The operation of unbinding reveals analogical relations that can be used in various applications as discussed in [27,52].

Holistic transformations for solving these problems are often illustrated using the well-known case of the “Dollar of Mexico” [27] in which a simple proportional analogy is considered: US:México::Dollar:?. This kind of analogy is known to be solvable by addition and subtraction of the embeddings of the corresponding concepts [40,50]. Similarly, in [49] these analogical retrieval problems are tackled via shallow ANNs using a dependency path of relations between terms in sentences. In conventional symbol manipulation (using geometric properties of the representation space) there is no direct analog to this kind of processing by holistic transformation. The holistic transformation of hypervectors can be seen as a parallel alternative to the conventional sequential search.

Learning systematic transformations from examples in the Holographic Reduced Representation (HRR) model [51] was investigated in [44,45]. A transformation hypervector is obtained from several training pairs of hypervectors as a solution to an optimization problem found by Gradient Descent, iterating through all examples until convergence. The learned transformation hypervector has been empirically proven to be able to generalize to new compositional structures with novel elements in structures of higher complexity than those provided as training examples. Similar capabilities with Binary Spatter Code (BSC) representations are illustrated in [25]. The drawback with such holistic transformations is their bidirectionality, which is due to the fact that in BSC unbinding is equivalent to binding. This complication can be solved by employing either the permutation or an additional associative memory similarly to the binding operation. A potential shortcoming of the approaches to learning holistic transformations is that the objects (and relations) are assumed to be dissimilar. Yet learning might not work as expected given that there is some similarity structure between the objects (relations) used as training examples. This is a direction that is worthy of further investigation.

Analogical reasoning In Cognitive Science, analogical reasoning theories [13] deal with analogical episodes (or analogs) and usually comprise (models for) a process55 comprising the following four basic steps:

The processing of analogical episodes involves two types of similarity. Structural similarity reflects the relations between the various elements of the episodes. Episodes are also matched in terms of a superficial similarity, which is based on common elements in episodes, or in terms of a broader notion of semantic similarity, which may be based on the similarity of characteristic feature vectors or on common membership in a taxonomic category.

HDC/VSA models have been used for analogical retrieval (see [52] and references therein). In such models both the set of structure elements and their arrangements influence the similarity of the corresponding hypervectors: similar episodes produce similar hypervectors. In [32] various studies are described which prove that results obtained by similarity estimation on hypervectors are consistent with both the empirical results in psychological experiments and the leading traditional models of the analogical retrieval.

Regarding the task of analogical mapping, models of mapping have been proposed that use techniques based on holistic transformations (again, see [32]). One of the limitations of these models is scalability. The similarity of hypervectors of the analogical episodes can be considered for their mapping. However, so far this approach was proved to work only for straightforward mapping cases. Several alternative mapping techniques have been proposed (including direct similarity mapping, re-representation by substitution of identical hypervectors, and parallel traversing of structures using higher-level roles). Some of them have been demonstrated on complex analogies. However, the techniques are quite elaborate and use sequential operations.

Interestingly, the hyperdimensional vector models adopted for analogical reasoning are compatible with established formats of knowledge representation, such as KGs. This facilitates the unification of symbolic and sub-symbolic approaches for cognitive modeling and AI. An interesting study in this direction has presented a proof of concept of the mapping between an RDF-Schema ontology and a HDC/VSA model [39].

Transformations of original data into hypervectors allow constructing hyperdimensional models for various application areas preserving the form of similarity that is relevant for a particular application [32]. This provides a tool to use HDC/VSA for similarity-based reasoning comprising (unsupervised) similarity indexing/search and (supervised) classification in its simplest form as well as much more advanced analogical reasoning techniques.

6.Learning

Classification is currently one of the most common application areas for of HDC/VSA, especially applied to images, signals and biomedical data in general (see [11,32] for detailed surveys). Similarity-based classification for vectorial representations of the instances are widespread in machine learning. A taxonomy of classification methods with HD models can be based on the headings level they focus on: primarily (first-level headings) we have methods devoted to the transformation of input data into hypervectors. Higher-level headings suggest further directions for applying HDC to classification, focusing on the types of input data (second-level headings) and on the domains (third-level headings), respectively.

In a basic classification methodology [11], during the training phase, an encoder employs randomly generated hypervectors (stored in the item memory) to map the training data into the hyperdimensional space. Then K class hypervectors are learned and stored in the associative memory. In the inference phase, the encoder generates the query hypervector for each test data. Then, a similarity comparison is performed in associative memory involving the query and each class hypervector, to finally predict the most similar class.

Simple models based on centroids are known to fall short in terms of generalization [29]. Improvements can be obtained by weighting newly assigned instances to the centroids [16]. It has been observed that conventional classifiers assume that the input vector components can be interpreted independently. This is reasonable when components are features endowed with meaningful interpretations. However, it is not generally applicable to HD representations [32]. Sparse HDC/VSA representations may be adequate for classifiers that benefit from sparsity, such as Winnow [35] and sparse Support Vector Machines [6].

Devising suitable encodings for good classifiers is a challenging task [9] worth of specific investigations: an appropriate choice of the encoding method is crucial for an accurate classification. For example, specific efficient encodings for biosignal processing are presented in [54]. Alternatively, different encoding methods can be integrated together to achieve higher accuracy [20]. Compared to single-pass training, retraining iteratively has been demonstrated to improve the accuracy of the classification models [21]. This suggests the direction of investigating ensemble (hierarchical) models of encoders (e.g., see [62]).

Competitive learning models are neural methods in which a number of groups/units compete to gain the responsibility of representing the incoming instances. They implement an online clustering algorithm, such as online k-Means and Leader Cluster, via neural extensions like Adaptive Resonance Theory [2] or Self-Organizing Maps [33]. These can be thought as local models for defining the input density which could be interestingly transposed to an HD representation. Probability density estimation (and other tasks such as kernel smoothing) have been shown to be efficiently tackled resorting to fractional power encoding [7]. An efficient algorithm in the context of such vector spaces has been presented in [15].

Once the instances are localized, a higher layer of units can be considered in the network architecture to perform supervised learning, leading to the definition of neural models, such as the Radial Basis Function networks [43] or the Mixture of Experts [23] This layer implements a local model for the generation of the output (classification/regression). Centroids have been shown to be easily combined with generalized Learning Vector Quantization classifiers [5]. Besides, moving from the idea of multiple-class hypervectors, disjunctive or mixture hierarchical representations of the classes may be targeted to better represent them [11].

Resorting to a HD representation, instances and cluster prototypes may be embodied by hypervectors and the mentioned clustering and classification/regression models may be implemented on HDC/VSAs. In the spirit of explainable AI, methods for the induction of (probabilistic) rules based on local models (basis functions) [60] could also be implemented on HDC/VSAs.

Structured data are generally more difficult to handle with conventional learning models, since local representations of structured data might not be convenient to use with vector classifiers, especially when hierarchies are involved. HDC/VSA models may be well suited for structured data, since they allow representing various structures (including hierarchies). Related to this task, we will deal with the case of problems regarding embedding models and knowledge graphs in §6.2.

An example of application field for such methods is chemio-informatics where classification models have been proposed to predict the properties of chemical compounds demonstrating state-of-the-art performance (e.g., see [24]). As an example, MoleHD [37], based on a representation of 2D molecular structures, demonstrated comparable results, on average, with respect to baseline drug discovery methods at much lower computational costs. More generally, the problem of classifying graphs using HDC/VSA is another promising direction for further investigations. In [48] it was shown that representing a graph as a superposition of hypervectors corresponding to vertices and edges, the resulting approach could achieve comparable results to standard baseline approaches on four out of six graph classification datasets while requiring much shorter training time.

7.Further perspectives for future work

Although HDC based on VSAs is no longer in its early stage it can still offer several directions for further improvement. These lines include (but are not limited to):