Learning with Holographic Reduced Representations
Year: 2022

Abstract:
Holographic Reduced Representations (HRR) are a method for performing symbolic AI on top of real-valued vectors [1] by associating each vector with an abstract concept, and providing mathematical operations to manipulate vectors as if they were classic symbolic objects. This method has seen little use outside of older symbolic AI work and cognitive science. Our goal is to revisit this approach to understand if it is viable for enabling a hybrid neural-symbolic approach to learning as a differentiable component of a deep learning architecture. HRRs today are not effective in a differentiable solution due to numerical instability, a problem we solve by introducing a projection step that forces the vectors to exist in a well behaved point in space. In doing so we improve the concept retrieval efficacy of HRRs by over 100⇥. Using multi-label classification we demonstrate how to leverage the symbolic HRR properties to develop an output layer and loss function that is able to learn effectively, and allows us to investigate some of the pros and cons of an HRR neuro-symbolic learning approach. Our code can be found at https://github.com/NeuromorphicComputationResearchProgram/ Learning-with-Holographic-Reduced-Representations

heading: 1 Introduction
text: Symbolic and connectionist (or “neural”) based approaches to Artificial Intelligence (AI) and Machine Learning (ML) have often been treated as two separate, independent methods of approaching AI/ML. This does not need to be the case, and our paper proposes to study the viability of a hybrid approach to propagation based learning. In particular, we make use of the Holographic Reduced Representation (HRR) approach originally proposed by Plate [1]. Plate proposed using circular convolution as a “binding” operator. Given two vectors in a d dimensional feature space, x,y 2 Rd, they can be “bound” together using circular convolution, which we denote as s = x ⌦ y. This gives us a new result s 2 Rd. The HRR approach also includes an inversion operation † that maps Rd ! Rd. With this binding and inverse operation, Plate showed that we can assign vectors to have a conceptual symbolic meaning and construct statements (or “sentences”) from these representations. For example, we can construct S = red ⌦ cat + blue ⌦ dog to represent “a red cat and a blue dog”. HRRs can also query the statement representation S. To ask which animal was red, we compose S ⌦ red† ⇡ cat which gives us a numeric output approximately equal to the vector representing “cat”.
The HRR framework requires a constant amount of memory, relies on well-optimized and scalable operations like the Fast Fourier Transform (FFT), provides symbolic manipulation, and uses only differentiable operations, that would make it seem ideal as a tool for exploring neuro-symbolic modeling. Unfortunately back-propagating through HRR operations does not learn in practice,
⇤Research work completed prior to joining Amazon.
35th Conference on Neural Information Processing Systems (NeurIPS 2021).
rendering it seemingly moot for such neuro-symbolic research. The goal of this work is to find sufficient conditions for successful back-propagation based learning with the HRR framework, and to develop evidence of its potential for designing future nero-symbolic architectures. Because the utility of HRRs for cognitive-science tasks are already well established, our application area will focus on a multi-label machine learning task to show how HRRs can provide potential value to research in areas it has not been previously associated with.
Backpropagating through HRRs is ineffective if done naively, and our goal is to show how to rectify this issue with a simple projection step and build viable loss functions out of HRR operations. We choose to do this with eXtreme Multi-Label (XML) classification tasks as one that is impossible for HRRs to tackle today. XML tasks have an input x, from which we have a large number L of binary prediction problems Y1,Y2, . . . ,YL. Our approach will be to represent each of the L classes as a HRR concept vector, and construct an alternative to a fully connected output layer that uses the HRR framework for learning. Our experiments and ablations will focus on the impact of replacing a simple output layer with HRRs and other changes to the HRR approach to better understand its behaviors. State-of-the-art XML performance is not a goal.
Our contributions and the rest of our paper are organized as follows. In §2 we discuss prior approaches related to our own, and how our work differs from these methods. In §3 we give a brief overview of the HRR operator’s details given its niche recognition within the AI/ML community, and introduce a simple improvement that increases the binding stability and effectiveness by 100⇥. Then in §4 we show how we can leverage HRR’s symbolic nature to create a new output layer and loss function combination that provides several benefits to deep extreme multi-label models. With this new method we demonstrate in §5 that compared to a simple fully-connected output layer we can reduce the output size by as much as 99.55%, resulting in a total reduction in model size by up to 42.09%, reduce training time by 41.86%, and obtain similar or improved relative accuracy by up to 30%. We also show that these results are often competitive with more advanced approaches for XML classification, though do still suffer at the largest output spaces with 670k labels. Finally we conclude in §6.

heading: 2 Related Work
text: Smolensky [2] elucidated early arguments for neuro-symbolic approaches with the Tensor Product Representation (TPR) that defined the first Vector Symbolic Architecture (VSA), defining binding and unbinding operations that allow symbolic style object manipulation atop some vector field. As argued by Smolensky [2] (and echoed by Greff et al. [3]), symbolic logic has greater power for complex tasks, but is brittle in requiring precise specification, where connectionist deep learning is more robustly able to process the raw inputs to a system, its capacity for more powerful “logic” is still limited and hotly debated. Combining these two domains in a neuro-symbolic hybrid system may yield positive results, and several recent works have found success in natural language processing tasks by augmenting recurrent neural networks with TPR inspired designs [4–6]. However, binding n vectors that are each d dimensions requires O(dn) space using TPRs. Thus VSAs that require a fixed dimension are computational preferable, but no work to our knowledge has successfully used a VSA of fixed length in gradient based learning. Schlegel et al. [7] provide a comprehensive summary and comparison of fixed length VSAs, and the details of how we chose to select HRRs based on their potential for gradient based learning and compute/memory efficacy in current frameworks like PyTorch are presented in Appendix D. Though such fixed-length VSAs have not been used in gradient based learning, they have still proven effective low-power embedded computation enviroments due to low-level hardware optimizations possible with many VSAs [8, 9].
The HRR operation has found significant use in cognitive science to create biologically plausible models of human cognition [10–13]. These approaches use the HRR’s operations in a primarily symbolic fashion to demonstrate human-like performance on a number of cognitive science tasks [14]. The vector representation is used as the foundation for biological plausibility after establishing that the operations required to implement HRR are within the plausible sphere of a biological substrate [15]. When learning has been incorporated in these models it has been primarily through examples of Hebbian updates of spiking models on the outputs of HRR, rather than back-propagation through the HRR operations and preceding inputs/layers [16]. In our work we advance the understanding of how to learn through the HRR through propagation in an effective manner and how HRR can be leveraged as an integral part of a neural-symbolic approach.
Little work exists on gradient based learning with HRR operations explicitly. The only work we are aware that attempts to leverage the symbolic properties of the HRR is by Nickel et al. [17], who use the binding operations to connect elements in a knowledge graph as a kind of embedding that combines two vectors of information without expanding the dimension of the representation (e.g., concatenation would combine but double the dimension). More recently Liao and Yuan [18] used circular convolution as a direct replacement of normal convolution to reduce model size and inference time, without any leverage of the symbolic properties available within HRRs. While Danihelka et al. [19] purport to embed the HRR into an LSTM, their approach only augments an LSTM by including complex weights and activations2, and does not actually use HRR as it lacks circular convolution, and all three works do not leverage the inverse operation † or seek to leverage any symbolic manipulations. By contrast our work explicitly requires the symbolic manipulation properties of HRR to create a vector-symbolic loss function, and we need to leverage the inverse operator †, meaning we use the entire HRR framework. We also demonstrate new insights into learning with HRR operations that make them more effective, where prior works have simply used the ⌦ operator on  2 components without further study.
There has been other work in differentiable neuro-symbolic systems outside of TPRs and VSAs, most notably using first-order logic [20–22]. These works represent another powerful alternative approach, though at this time are often more involved in their design and training procedures. We consider these beyond the scope of our current study, where we seek to obtain similar benefits using the simpler HRR that requires only the careful application of FFTs to leverage. This is an easily satisfiable constraint given their heavy optimization and wide spread use amongst existing deep learning frameworks.
Our use of extreme multi-label classification problems is due to it being out-of-reach of current HRR methods, which we found produced random-guessing performance in all cases. There exists a rich literature of XML methods that tackle the large output space from the perspective of decision trees/ensembles [23–27], label embedding regression [28–31], naive bayes [32], and linear classifiers [33, 34]. There also exist deep learning XML methods that use either a fully-connected output layer [35] and others that use a variety of alternative approaches to dealing with the large output space [36–43]. The variety of approaches is orthogonal to the purpose of this work, which is to investigate HRRs. We will leverage only some of these works to modify their architectures to use a fully-connected output layer (if they do not already) and to use our HRR approach, so that we can observe the impact of the HRR specifically on the model. In our experimentation we found that the mechanisms for handling the high cardinality of outputs is highly architecture tuned and specific, making it difficult to do broader comparisons. Our work will explore fully-connected, convolutional, and recurrent architectures to show that our HRR approach can work broadly across many types of architectures that have been used, but it is not our goal to be the “best” at XML by any metric. The XML task’s value to our study is a problem that current HRR methods could not tackle, and where we can apply the symbolic properties of HRR in developing the solution in a way that demonstrates how one may design HRR based networks for other tasks.

heading: 3 Holographic Reduced Representation
text: The original paper by Plate [1] introduced the HRR approach and developed significant theory for its use as a symbolic approach to AI on a neural substrate. We will quickly review its foundation and numerical issues that lead to our projection based improvement. The HRR starts with circular convolution as a “binding” operator. We use Plate’s notation of ⌦, and a definition of circular convolution using an FFT F and inverse FFT (F 1) is given in eq. (1). It is easy to see that the binding operator of circular convolution ⌦ is commutative. What is particularly interesting is the ability to unbind terms that have been bound by this operator. Let F(a)i denote the i’th complex feature of the FFT of a. By defining an identity function F(a†)iF(a)i = 1, we can derive the inverse function eq. (2), where we raise each complex coefficient zi of the FFT to the z 1i power before going back to the real domain.
a⌦ b = F 1 (F(a) F(b)) (1) a † = F 1
✓ 1
F(a)
◆ (2)
2HRRs & circular convolution can naturally exist in the reals.
Using this, Plate [1] showed that one can compose sentences like our example S = red⌦cat+blue⌦ dog by assigning concepts to vectors in a d dimensional space. We can unbind components with the inverse operation, giving S ⌦ cat† ⇡ red , or we can check for the existence of a term by checking that S>cat† ⇡ 1. A term not present, like “cow”, would behave as S>cow† ⇡ 0. These sentences can be constructed with more complex logic. The binding is also distributive (and associative), so a⌦ (x+ y) = a⌦ x+ a⌦ y. This allows us to construct complex symbolic relationships. As an example, we could have: S = first⌦(name⌦Jane+age⌦30)+second⌦(name⌦Joe+age⌦33), and to determine the name of the first person we can perform first† ⌦ name† ⌦ S ⇡ Jane .
To make this symbolic manipulations effective, Plate [1] introduced two points of sufficiency. First, a vector a used for HRR operations should have its values sampled from a normal distribution: a ⇠ N 0, Id · d 1 . This allows binding and unbinding to work in expectation. Second, is that the inverse † is numerically unstable. The remedy developed is the pseudo inverse ⇤, given by a⇤ = [a1, ad, ad 1, . . . , a2]. This approximation was justified by noting that in polar form one obtains Fj
a† = 1rj e i✓j and Fj (a⇤) = rje i✓j , which are off by the reciprocal of the complex magnitude. Plate and others [14] use the pseudo inverse ⇤ exclusively as the error due to approximation of † was smaller than the errors caused by numerical instability. In Appendix B we provide additional illustration about the potential modeling with HRRs, and worked examples demonstrating why the math works is provided in Appendix B.

heading: 3.1 Improved HRR Learning
text: The only prior work backpropogating through ⌦ only needed to bind two items together at a time [17], where we need to bind and represent tens-to-hundreds of thousands of concepts. Prior work also made no use of the unbinding with †, which we require. We found that the default method proposed by Plate [1] was not sufficient for our work, and needed improvement. In particular, we needed better detection if a vector y (read, label) has been bound to a statement S (read, output). We achieve this by defining a new complex unit magnitude projection, which is given by eq. (3).
⇡(x) = F 1 ✓ . . . ,
F(x)j |F(x)j | , . . .
◆
(3)
We change the initialization to a ⇠ ⇡ N 0, Id · d 1 which ensures the vectors we use for HRR operations are unitary, meaning the complex magnitude is one. In this case we obtain a† = a⇤ because in polar form we have rj = 1 8j, giving Fj a† = 11e i✓j = Fj (a⇤) = 1e i✓j .
This has a number of benefits. First, we make the numerically stable ⇤ have a mathematically equivalent result to the true inverse, removing that source of error. Second, the ⇤ is faster to calculate requiring a simple shift of values that takes O(d) time to perform, compared to O(d log d) for the FFTs in †. Third, we find that this complex projection significantly increases the number of concepts that can be bound together and the accuracy of retrieving them. Using standard HRR initialization we found it difficult to use more than 10 bindings in a statement, but our simple change allows us to improve query accuracy by up to 100⇥ as many bound vectors.
To demonstrate the effectiveness of our projection step, we create a statement vector S =PT
i=1 ai⌦bi. We can ask if two vectors x⌦y 2 S by checking that x>(S ⌦ y†) ⇡ 1. If the pair are not bound in S, then x>(S ⌦ y†) ⇡ 0 meaning x ⌦ y /2 S. We explicitly use this problem formulation because it is integral to our approach to XML. This is shown for a 256 dimension space in Fig. 1 where the black dashed
line marks the “in” case and the dotted black line the “not in” case. Notice that the naive HRR approach has present values that look absent, and absent values that look present, with unexpectedly large and small magnitudes. The variance of naive HRR also increases as the number of terms bound together increases. In contrast, our projection ⇡ keeps the response around 1 and 0 for present and absent tokens respectively, even when binding 1024 vectors in only 256 dimensions. This is critical for us to represent large output spaces in a smaller source dimension, and removes the need for complex averaging and associative cleanup approaches attempt by Danihelka et al. [19]. Plate’s original theory indicated binding capacity would increase linearly with dimension size d, which we found did not hold for naive HRRs, but does for our projected variant. Additional details and experiments on binding capacity, and selection of HRRs as opposed to alternative binding operations, is provided in Appendix D.

heading: 4 Dense Label Representations
text: Now we will define our new neuro-symbolic approach to XML tasks by leveraging the HRR operations with our improved initialization from §3.1. We define L as the number of symbols (or labels) in the given task dataset. We will use a d0 ⌧ L dimensional output space Rd0 , which is a hyperparameter we can choose. We will define two vectors p,m 2 Rd to represent the concepts of a class being present and missing (or “negative” / “absent”) from the label space Y1,...,L. We initialize p ⇠ ⇡(N (0, Id · d0 1)), and then select m to be any vector orthogonal to p.
We now define some additional notation and terms to describe our approach. We will use Yp to denote the set of ground truth labels present for a given datapoint x and Ym for the missing labels, where Yp [ Ym = Y1,2,...,L. For every individual classification problem Yi, we will use ci ⇠ ⇡(N (0, Id · d0 1)) to represent each class with a vector. The vectors p,m, c1,2,...,L will all be initialized as we have described, and will not be altered during training. To denote the neural network we will train and its output, we will use f(x) = ŝ 2 Rd0 .
HRR Label Vector: We begin by converting the labels for a data point x into a labels vector s 2 Rd0 . This vector s will be constructed using the HRR framework to be a neuro-symbolic representation of the original labels, and is defined by eq. (4). Thanks to the the commutative property of ⌦, the “present” vector p can move outside the summation and be bound with all present classes, and the non-present vector m can be bound with every item not present. This will create a statement s with technically hundreds of thousands of bound components that we could query. We can compute this efficiently in O(|Yp|) by computing once the “all labels” vector A = PL i=1 ci. This is done once at initialization, and then we can re-write eq. (4) into the more efficient form of eq. (5), leveraging the symbolic properties of HRR to avoid computation.
s =
Labels presentz }| {X cp2Yp p⌦ cp + Labels absentz }| {X cm2Ym m⌦ cm (4) = p⌦ X cp2Yp cp +m⌦
0 @A X
cp2Yp cp
1
A (5)
HRR XML Loss: We now have the output of our network ŝ and a target vector s that exist in a d0 ⌧ L dimensional space. A straightforward idea would be to take an embedding style approach to make the loss function `(s, ŝ) = ks ŝk22. This is intuitive and matches prior approaches to XML [28, 30]. However, we found that such an approach resulted in no learning and degenerate random-guessing performance. This is because the regression formulation targets the overall errors in exact values, rather than the real goal of being able to extract the present classes from ŝ. Because binding many values in a fixed dimension d0 introduces noise, the regression approach attempts to learn this underlying noise that is not meaningful to the actual problem.
Our solution to this issue is to again leverage the properties of HRR operations to create a loss based on our ability to accurately query the predicted statement s for the same components we would expect to find in the true label s. We remind the reader that we can query if a class cp 2 s by checking if s>c⇤p ⇡ 1. We normalize this dot product, i.e., use the cosine similarity cos(s, c⇤p) = s>c⇤p
kskkc⇤pk to
perform these queries in a manner that limits the response magnitude to [ 1, 1], which will prevent degenerate solutions that attempt to maximize magnitude of response over query efficacy.
With the bounded cosine response, our loss has two components. First we build a loss term that goes though all present labels Yp, checking that each can be extracted. This involves computing p⇤ ⌦ S to extract the symbolic statement representing all present vectors (i.e., p⇤ ⌦ S ⇡
P cp2Yp cp). Then we
use each label HRR vector cp and check if it is present in the extracted output. This results in eq. (6)
Next we confirm that the absent labels (the vast majority) are not queryable from the output. Rather than enumerate all L |Yp| labels, or perform lossy negative sampling, we can instead leverage the symbolic properties of HRR. We will compute m⇤⌦ s to extract the representation of all non-present classes, and perform a dot product against all present classes that are expected. This gives us eq. (7).
Jp = X
cp2Yp (1 cos (p⇤ ⌦ ŝ, cp)) (6) Jn = cos
0 @m⇤ ⌦ ŝ, X
cp2Yp cp
1
A (7)
This negative component of the loss works because it is minimized by having the absent labels m⇤ ⌦ s and present labels P cp2Yp cp be disjoint (i.e., no overlap). If there is any overlap, the dot product between these terms will increase, and thus, increase the error.
Through this neuro-symbolic manipulation we can create a loss term that simultaneously considers the presence/absence of all L labels in only d0 ⌧ L dimensions and O(|Yp|) time. The final loss is simply `(s, ŝ) = Jp + Jn.
We remind the reader that the target label s is present in the form of knowing the exact cp 2 Yp vectors to use. One could, if preferred, denote this loss as `(Yp, ŝ). We also note that expectation may be that a new hyper-parameter is needed to balance between the relative importance of eq. (6) and eq. (7). However, we find that no such parameter is needed and simply adding them together is effective.

heading: 5 Experiments & Analysis
text: We will now conduct an experimental evaluation of our new HRR based approach to XML classification. We emphasize to the reader that this is to show that the HRR approach of symbolically modeling a goal, and then back-propagating through the vector-symbolic HRR, works and has potential utility broadly. We do not argue for “dominance” at the XML task or to supplant all current approaches. XML is simply a task we are applying the HRR to show the pros (and some cons) of the HRR approach. To this end we will show results with a Fully Connected (FC), Convolutional Neural Network (CNN) based network, and attention augmented Long-Shot Term Memory (LSTM) networks. The CNN and LSTM models are applied to every dataset for which the original text was available, only FC is applied to every dataset since fixed-length feature vectors were always provided3. Each will be endowed with our HRR dense label representations as described in §4 using our improved HRR initialization from §3 (becoming HRR-FC, HRR-CNN, and HRR-LSTM). The CNN & LSTM are taken from the XML-CNN [35] and AttentionXML [41] works. The AttentionXML’s hierarchical prediction head is replaced with a fully connected layer in our experiments because we are interested in studying the impact of FC ! HRR replacement, and how the change to an HRR impacts the standard network behavior. Using the XML tasks we will study the impact of the HRR an ablate choices like the use of fixed vs learned values for the p & m vectors, as well as the label vectors cp, impact of increasing the HRR dimension d0, and impact on model size and training time. We also ablated the impact of our projection step ⇡(·), and found that in all cases skipping the projection step caused degradation to random-guessing performance, and thus will not be explicitly included in results.

heading: 5.1 Datasets & Evaluation Metrics
text: To assess the impact of dense label representations, we use eight of the datasets from Bhatia et al. [44]. Table 6 (see appendix) provides statistics about each dataset used for experiments. The average number of samples per label varies from 2.29-1902.15, and the average number of labels per data point varies from 2.40-75.54. Bhatia et al. [44] split the dataset into small scale and large datasets depending on the number of labels in each input sample. Small scale datasets consist of at most 5000
3We did contact [44] for all text data but received no reply.
labels. The features are a bag-of-words representation of the text in every dataset. Negative labels are as much as 124321⇥ more populous than positive labels per point. TF-IDF style pre-processed features are available for all datasets, but the original text is not. We were unable to obtain the original text for all datasets, and models which require the original text (CNN & LSTM) thus are not tested when the raw text is not available.
We will consider two primary metrics in our evaluation that are common in XML work, Precision at k (P@k) and the propensity score at k (PSP@k). Given rankk(ŷ) as the rank of all the labels in ŷ and pl is the relative frequency of the l’th label, the P@k (Equation 8) measures raw predictive accuracy of the top-k guesses, and PSP@k (Equation 9) down-weights correctly predicting frequent classes to counteract the power-law distribution of labels common in XML problems.
P@k := 1
k
X
l2rankk(ŷ)
yl (8) PSP@k := 1
k
X
l2rankk(ŷ)
yl pl
(9)
For brevity we will focus on k = 1 in most experiments, but found that k 2 [1, 5] scores were all highly correlated and did not meaningfully alter any results. Additional metrics we considered are mentioned in Appendix F, but we found them so highly correlated with either P@k or PSP@k as to make them redundant.

heading: 5.2 Network Architectures
text: The baseline multi-label network is a fully-connected (FC) network with two hidden layers. Both hidden layers have the same size of 512 with a ReLU activation. The basline network has L outputs trained with binary cross entropy (BCE) loss with appropriate sigmoid activation. Our HRR version of this network (HRR-FC) uses the same architecture for input and hidden layers. But unlike the multi-label network, the output layer is significantly constrained (size is 512⇥ d0) where d0 is the size of dense label representation (§4 for more details). We note that this gives our HRR Network less parameters to solve the same problem, giving it a disadvantage in capacity.
For a CNN based model we will use the XML-CNN approach of [35]. Their original architecture with their code is used as the baseline, and our modified version (HRR-CNN) has the same architecture but replaces the output layer with the HRR approach as we used in HRR-FC just described. We note that the original code selected best results from the test set, leading to over-fitting. We have corrected this issue which prevents us from achieving the same results previously published.
For the LSTM model, we use the attention based bidirectional approach of AttentionXML [41]. The approach used for the output prediction of AttentionXML is involved in a hierarchical sequence of fully connected layers applied per output token to produce a single scalar output, which makes it non-viable to directly convert to an HRR based approach. For this reason we replace the final hierarchical prediction heads of AttentionXML with the same attention mechanism but use a standard fully-connected output layer like the FC and XML-CNN models do, and denote this as the “LSTM” model in results. Our version of AttentionXML with the dense HRR label approach is denoted as HRR-LSTM.
Our goal is not to determine the most accurate possible XML model, and for this reason we do not perform any expensive hyper-parameter search over the architectures for any of the six models considered (FC, CNN, LSTM, and HRR variants). Doing so to maximize model accuracy would require considering many parameters and source of variation to make a robust conclusion on accuracy[45], but leaves each model on each dataset to have potentially highly different parameters. This obfuscates our true goal[46], which is to understand the impact of the HRR modification in isolation. For this reason we hold as many other variables as constant (depth, layers, neurons per layer, etc) and stick to the defaults found to work well in prior work for non-HRR networks. This allows us to isolate the HRR’s impact, and intrinsically puts the HRR network at a disadvantage because it has fewer parameters.

heading: 5.3 XML HRR Accuracy
text: We first investigate how the smaller HRR space of d0 ⌧ L dimensions impacts each model’s accuracy. Table 1 shows the performance of HRR approach to its respective baselines, evaluated at k = 1 for brevity. For all datasets, dimension size d is 400 except in case of Amazon-13K, Wiki10-31K,
Delicious-200K and Amazon-670K where d is 3000. In many cases our HRR based model approaches the high accuracies of state-of-the-art work, which is informative in that our HRR approach can be implemented with 22 lines of code, compared to hundreds of lines of the more involved methods. We underline the datasets that were used in these prior papers and use a to denote being within 5% (relative) of scores reported by [35], and b for 5% of the original AttentionXML [41].
Each bold case shows HRR improving over its baseline. HRR-FC Bibtex improved 1.30 1.40⇥ and Delicious-200k’s P@1 improved 2.06⇥ despite a 1.52⇥ decrease in PSP@1. HRR-CNN improved the Wiki10-31K results by 1.24⇥. In most cases when the HRR results are not better, they are near the performance of the baseline. Most PSP@1 show a  1 point decrease, and relative decrease on P@1 results is minimal. The overall results indicate that the HRR approach is moderately worse for retrieval of low-frequency labels, but often significantly better at high-frequency labels (a trade off that is task specific). The primary outlier in behavior is the Amazon-670K dataset, which appears to be pushing the limits of the HRR approach’s ability to distinguish between the 670K label vectors. While this is a negative result in terms of XML, our goal was to improve HRRs: the ability to predict & retrieve the a correct label 19.9% of the time out of a space of 670K labels is a near three order of magnitude improvement over the naive HRR without our projection step, which could only perform accurate retrievals of fixed and known vectors in a space of < 10 total outputs.
The high relative performance of our HRR-FC compared to XML-CNN and AttentionXML, and our difficulty replicating XML-CNN when fixing the test-set validation bug, does pose interesting questions about the impact of model choice on XML benchmarks. Similar results have been found in systematic review & replication of work in information retrieval and triplet learning [47, 48], but such an investigation is beyond the scope of our work.
5.4 HRR Model Compression & Runtime Table 2: For each dataset the percentage reductionin parameters of the output layer, and the resulting change for the entire network, by replacing the output layer from a fully-connected softmax with our HRR approach.
Dataset Dim d0 % CompressionOutput Network Delicious 400 59.30 29.22
EURLex-4K 400 89.98 37.80 Wiki10-31K 3000 90.25 29.49 Amazon-13K 3000 77.49 4.74 Delicious-200K 3000 98.53 41.88 Amazon-670K 3000 99.55 42.09
Because of the size of the output space L, the output fully connected layer can represent an enormous amount of the weights within a neural network in this problem space. We can see in
Table 2 that the HRR approach can reduce the number of parameters in the output layer by 59- 99%, which accounts for 29-42% of the model’s total parameters in most cases. The mild exception is the Amazon-13k corpus, which has a large number of input features and comparatively smaller output space. This shows that
our HRR approach naturally provides a more compact representation that could be applicable for situations with a high arity of discrete outputs, yet allows learning in a continuous fashion without any sampling tricks.
Table 3: Speedup in training time for HRR-FC over the FC model. Bold indicates improved runtime.
Dataset Speedup
Bibtex 0.35 Delicious 0.38 Mediamill 0.39 EURLex-4K 0.35 Wiki10-31K 1.48 Amazon-13K 1.33 Delicious-200K 4.47 Amazon-670K 6.28
Fewer parameters leads to a natural speedup in training time too. Table 3 shows the optimization time for a training epoch for a multilabel baseline and HRR-FC where we see an up-to 6.3⇥ reduction in optimization time. The larger the output label space is relative to the rest of the network, the more advantage we obtain. The four cases where HRRs are slower are all the fastest cases, with the smallest dimensions, which prevent the overheads of the HRR implementation from fully realizing their benefit. This is because the cross-entropy calculations are highly optimized, and faster than the cosine similarity and for loops needed by our HRR implementation.
We note that separate from the training time, at inference time on the test set the HRR approach currently takes the same time as the fully-connected output. This is because each positive label cp is queried against the network’s output ŝ, but this need not be the case. There is further potential for improvement by developing specialized Maximum Inner Product Search (MIPS) kernels that interface nicely with PyTorch, don’t require memory copies, and can re-constitute the output labels as needed. These are all engineering challenges we consider beyond scope of the current work, as we are concerned with how to learn through HRRs.

heading: 5.5 Assessing Impact of Hyper-parameters
text: By demonstrating non-trivial learning that can match or even improve upon the accuracy of a standard fully-connected output layer that naturally leads to reductions in model size/memory use and improved training time as the models get larger, we have shown that our projection step makes HRRs viable for future learning tasks. This is because without our modification we get consistent random-guessing performance across all datasets.
However, our larger goal is to gain new information about how to learn with HRRs. As such we now perform a number of ablation experiments to elucidate potential factors relevant to future work outside of XML. This includes the impact of the output dimension d0, the effect of increasing model size, and if the HRR vectors should be altered via gradient descent or left static as we have done. Due to space limitations, we will show many results on just the Wiki10-31K dataset in this section as we found it tracks well with overall behavior on other corpora.
Label Dimension Size: While training a model with a dense label representation, the vector size d0 of the label is fixed. Figure 2 shows the impact of vector dimension size on the model’s precision. As observed, Precision@5 increases when the dimension size is increased (and is representative of other metric’s behavior). For datasets Wiki10-31K and AmazonCat-13K, the precision begins to plateau when the dimension size is approximately 10% of the number of labels in that dataset. The trend is consistent across all Precision@k measurements. For a larger dataset like Delicious-200K, the precision levels off at
a dimension size of 2500, which is 1.25% of the number of labels. Thus, Figure 2 suggests that HRR can substantially compress the size of the label vector as the number of labels increases (and with it the label distribution itself is increasingly skewed).
Network Layer Size: Our initial results in §5.3 showed that our HRR-FC & HRR-CNN have comparable or better accuracy, while also having less parameters. We also looked at how these results would change as both models are made larger. Results from Wiki10-31K are
HRR
3 512 400 55.06 3 2048 400 55.36 3 2048 750 56.84 3 2048 1500 57.80 3 2048 3000 58.51
shown in table 4. We can see that even moderate changes to the baseline network actually produce a drop in accuracy, which is expected since we tuned the initial architecture to baseline performance. For our HRR-FC more layers or hidden neurons have minor impact, but combined with larger output size d0 can increase performance from the initial 53.25% up to 58.51%. All of these HRR-FCs still have fewer parameters than the initial baseline network.
Updating p & m Vectors: The p and m vectors are the key to the cumulative positive and negative class vectors. It is possible to backpropagate to these vectors and alter them during training, rather than hold them fixed as we have done. We measure the impact of updating p and m vectors in comparison to keeping them static while the model is being trained. We found that maintaining p and m vectors fixed is beneficial when the dimension size is small (d0  400). As d0 increases we observe no impact from learning the values of p and m. This was consistent across all datasets and architectures.
2048 3000 58.51 58.18
Updating Label Vectors cp: Another question is if we should have allowed the label vectors cp to be altered during training, rather than holding them fixed at initialized values. We test this in Table 5 using a network with multiple different numbers of hidden neurons h and output dimensions d0 for a 2-layer network, where the rcp is the performance when we allow the concept vectors to be learned. We note that this was implemented by always back-propagating through our complex unit magnitude projection ⇡, and resulted in no significant performance difference. Experiments without the projection ⇡ had significantly degraded results that gave random-guessing performance.
These experiments show that altering the HRR vectors, at least in the XML application, have no benefit. We had expected this to perform better by giving the network a chance to adjust for any unfavorable initialization. Our current hypothesis is that the network’s own parameters are sufficient to learn how to leverage the dynamics of HRR operations, which should still encourage the same properties while training, making the weights of the HRR concept vectors redundant. Further exploration of this is needed in future studies.

heading: 6 Conclusion
text: We have improved the initialization of HRRs to increase binding and retrieval accuracy, allowing for a convenient & differentiable neuro-symbolic approach. To demonstrate potential utility we have applied HRRs to extreme multi-label classification. We observe reduced model size, faster training, and stable-to-improved accuracy. This provides evidence for the general utility and further study of HRRs. The learning dynamics of HRRs are not yet fully understood by our work and have the counter-intuitive behavior that learning with them, but not altering them, tends to have the best results. Compared to prior works looking at HRRs we have significantly improved the viability of building more complex networks that leverage the symbolic manipulation properties of HRRs, which opens the door to a new kind of approach to modeling problems.

Review summaries:
This paper introduces a modification to the Holographic Reduced Representation (HRR) method, which are a pair of encoding/decoding operations based on circular convolution; these operations can be used to efficiently approximate symbolic querying, information storage, and retrieval operations in a low-dimensional vector embedding space.  used for approximating symbolic storage and retrieval operations.  The first contribution of this paper is a modification to the original HRR method (introduced by Plate 1995 and primarily used in biologically-plausible computation models) that increases its query accuracy.  The second contribution to this paper is a proof-of-concept loss function that allows the modified HRR encoding to be incorporated into differentiable neural architectures.  The final contribution of this paper is a set of experiments showing that concrete HRR-based models can be used in extreme-multi-label (XML) classification tasks, in some cases exceeding baseline accuracy with standard fully-connected layers used for lookup and retrieval (while using a comparatively smaller and more efficient encoding/decoding scheme.)

The authors introduce an improved formulation of learning using holographic reduced representations (HRRs). The paper shows that the improved HRR formulation allows HRRs to be used for eXtreme Multi-Label (XML) classification tasks, and that using an HRR-based approach leads to improved performance over FC, CNN and LSTM baselines. In addition to comparing against baselines, the paper also assess the impact of various hyperparameters. 

The authors improve Plate's HRRs, which opens up new possibilities for differentiable neuro-symbolic components in neural networks. The authors demonstrate the effectiveness of the introduced projection step in one setting: extreme multi-label problems. The paper is very well written, and the results are convincing with an exemplary analysis.

This paper investigates the technique of “Holographic Reduced Representation” (HRR), developed in the early 90’s by Tony Plate as a tool for symbolic reasoning, for use in modern neural network architectures trained using backpropagation. The authors find that Plate’s original formulation leads to low accuracy in this setting and present a simple fix that improves performance. The authors apply the technique to classification problems in which the outcome is a high-dimensional binary vector and show that HRRs can be used effectively in conjunction with gradient based training methods in this setting. The paper is well written, technically sound, and discusses an interesting avenue for bridging classic work on connectionist AI with more modern techniques.