Learning with Holographic Reduced Representations
Authors: Ashwinkumar Ganesan
Hang Gao
Sunil Gandhi
Edward Raff
Tim Oates
James Holt
Mark McLean
Venue: NeurIPS 2021 Spotlight (2021)
Keywords: Holographic Reduced Representations
binding
neuro-symbolic

Abstract: Holographic Reduced Representations (HRR) are a method for performing symbolic AI on top of real-valued vectors 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 differential component of a deep learning architecture. HRRs today are not effective in a differential 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\times$. Using multi-label classification we demonstrate how to leverage the symbolic HRR properties to develop a 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. 

Learning with Holographic Reduced Representations
Ashwinkumar Ganesan' 1 Hang Gao', Sunil ; Edward Raff!-2,, Tim Oates!
James Holt", Mark McLean2
l University of Maryland, Baltimore County
Laboratory for Physical Sciences
Booz Allen Hamilton
Abstract
Holographic Reduced Representations (HRR) method for performing symbolic Al on top of real-valued vectors [ by associating each vector with an abstract concept, and providing mathematical operations to manipulate vectors 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-symbot learning differentiable component of deep learning architecture. HRRs today are not effective in differentiable solution due to numerical instability, problem we solve by introducing projection step that forces the vectors exist in well behaved point in space. In doing so we improve the concept retrieval efficacy of HRRs by over 100x. Using multi-label classification we demonstrate how leverage the symbolic HRR properties to develop an output layer and loss function that is able learn effectively, and allows us investigate some of the pros and cons of an HRR neuro-symbolic learning approach. Our code can be found at http:p//gggtttt.o////////aaaaaaa
approach to
Introduction
Symbolic and connectionist (or "neural") based approaches 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 (I]. Plate proposed using circular convolution "binding" operator. Given two vectors in d dimensional feature space, æ; y E Rd, they can be "bound" together using circular convolution, which denote result & E T The HRR approach also includes an inversion operation i that maps Rd -> RRd
y. This gives
With this binding and inverse operation, Plate showed that we can assign vectors to have 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 8 red! as cal which gives us a numeric output approximately equal to the vector representing "cat".
The HRR framework requires constant amount of memory, relies 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 paok-propggating through HRR operations does not learn in practice,
Research work completed prior to joining Amazon.
35th Conference on Neural Information Processing Systems (NcurIPS 2021).

---

rendering it seemingly moot for such neuro-symbolic research. The goal of this work is to find sufficient conditions for successful baok-poopngntion 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-Labe (XML) classification tasks as one that is impossible for HRRs to tackle today. XML tasks have an input æ. from which we have large number L of binary prediction problems V/.J/.....,. Vi.. Our approach will be to represent each of the L classes as HRR concept vector, and construct an alternative to fully connected output layer that uses the HRR framework for learning. Our experiments and ablations will focus on the impact of replacing simple output layer with HRRs and other changes to the HRR approach to better understand its behaviors. ofate-of-the-art XML performance is not goal.
Our contributions and the rest of our paper are organized as follows. In $ we discuss prior approaches related to our own, and how our work differs from these methods. In $
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 100x. Then in $ we show how we can leverage HRR's 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 $5that compared to 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 $
2 Related Work
Smolensky elucidated early arguments for neuro- ceuro-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. Bl), 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 system, its capacity for more powerful "logic" is still limited and hotly debated. Combining these two domains in a neuro-symbolie hybrid system may yield positive results, and several recent works have found success natural language processing tasks by augmenting recurrent neural networks with TPR inspired designs 44 However, binding n vectors that are each d' dimensions requires (dd)) 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 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 Apppendix 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 [0-13. These approaches use the HRR's 's operations in primarily symbolic fashion to demonstrate human-like performance on 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 biological substrate
[5]. 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 baok-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 integral part of neural- symboliy approach.
2

---

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 by Nickel et al. [17. who use the binding operations to connect elements in a knowledge graph as 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 [ used cireular 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 activations I and does not actually use HRR as it lacks circular convolution, and all three works do not leverage the inverse operation f or seek to leverage any symbolic manipulations. By contrast our work explicitly requires the symbolic manipulation properties of HRR to create vector-symbolic loss function, and we need to leverage the inverse operator f. 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 S 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 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 due to it being out-of-reach of current HRR methods, which we found produced random- -uulssing 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
27 label embedding regression [S111 naive bayes [2), and linear classifiers There also exist deep learning XML methods that use either fully-connected output and others that use a variety of alternative approaches to dealing with the large output 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 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 mechanisms for handling the high cardinality of outputs is highly architecture tuned and specific, making it difficult 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 s value to our study is 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.
3
layer K35
space 36
the model. In our experimentation we found that the
3 Holographic Reduced Representation
The original paper by Plate M introduced the HRR approach and developed significant theory for its use as a symbolic approach to AI on neural substrate. We will quickly review its foundation and numerical issues that lead to our projection based improvement. The HRR starts with circular convolution "binding" operator. We use Plate's notation of @, and a definition of circular convolution using an FFT J and inverse FFT (F-1) is given in eq. ( 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), denote the i'th complex feature of the FFT of a. By defining an identity function F(a)),F((); = 1, we can derive the inverse function eq. (2). where we raise each complex coefficient 2, of the FFT to the 2, power before going back to the real domain.
2 F (F(a) o F(b))
(1)
at = J-1
(((a)
(2)
PHRRs& & circular convolution naturally exist in the reals.
3

---

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 dimensional space. We can unbind components with the inverse operation, giving S @ cal R red, or we can check for the existence of a term by checking that S catt 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 + agee second & (name @ Joe + age@33), and to determine the name of the first person we can perform first" @ name! @) S Rs Jane.
To make this symbolic manipulations effective, Plate 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, La d This allows binding and unbinding to work in expectation. Second, is that the inverse f is numerically unstable. The remedy developed is the pseudo inverse given by a' = = Od, dd-11...... U2]. This approximation was justified by noting that in polar form one obtains F, (a') = 18, and F3 (a") = rrree= "0,,, 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 Appppdixx B we provide additional illustration about the potential modeling with HRRs, and worked examples demonstrating why the math works is provided in Appendix B
3.1 Improved HRR Learning
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-hundred of thousands of concepts. Prior work also made no use of the unbinding with i. which we require. We found that the default method proposed by Plate [I]] was not sufficient for our work, and needed improvement. In particular, we needed better detection if vector y (read, label) has been bound to a statement S (read, output). We achieve this by defining new complex unit magnitude projection, which is given by eq. (
We change the initialization to a π (N (0, Lo 1) which ensures the vectors we use for HRR operations are unitary, meaning the complex magnitude one. In this case we obtain at = a" because in polar form we have ry 1 Vj. giving F, (at) _e te- 18, F, (a*) = 1e- i0.
F(m)) [F(x))]
T(x) F
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 Odd log d) for the FFTs in t. Third, we find that
Naive Present
Average response of xt (S (S@v)
Proj ir-)) Present
Naive Absent
Proj x(-) Absent
this complex projection significantly increases the number of concepts that can be bound to- gether and the accuracy of retrieving them. Us-
ing standard HRR initialization we found it dif- ficult to use more than 10 bindings in a state- ment, but our simple change allows us to im- prove query accuracy by up to 100x as many bound vectors.
-2-
200
400
600
800
1,000
Number of bound terms
To demonstrate the effectiveness of our projec- tion step, we create statement vector S = CL.4, We can ask if two vectors x &gy e S by checking that x T(S & y') x 1. If the pair are not bound in S, then x TT TS yi) ~ 0 meaning x & y & S. We explicitly use this problem formulation because it is integral to our approach to XMI.. This is shown for 256 di- mension space in Fig. D where the black dashed
Figure 1: Demonstration of the HRR query check- ing if x @ y the HRR vector If present, the response value (y-axis) should return 1=.0 (dashed line). If absent, the response should x: (dotted line). Naive use of HRR (blue & green) results in more noise with present and absent results both returning values far above and below the expected range [0, 1). Our projection π (orange red) keeps values stable and near their expected values.
4

---

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 and O 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. [I9]. Plate's 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
Dense Label Representations
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 T. as the number of symbols (or labels) in the given task dataset. We will use a d' < L dimensional output space Rd", which is hyper- parameter we can choose. We will define two vectors p, m E Rd to represent the concepts of a class being present and missing (or "negative"/ / "absent") from the label space V/...... We initialize TTV Ta d) and then select m to be any vector orthogonal to p.
We now define some additional notation and terms to deseribe our approach. We will use y' to denote the set of ground truth labels present for a given datapoint æ and ymm for the missing labels, where ) U U 2. For every individual classification problem V. we will use C, (O, Ia d' d) represent each class with a vector. The vectors p, m, C1.2..., 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 fxx = E RR...
We begin by converting the labels for a data point x into labels vector s E R This vector will be constructed using the HRR framework to be a neuro symbbllc representation of the original labels, and is defined by eq. 4 Thanks to the the commutative property of (9, 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 ((DP)) by computing once the "all labels" vector Σ Cs. This done once at initialization, and then we can re- re-write eq. 4 into the more efficient form of eq. leveraging the symbolie properties of HRR to avoid computation.
HRR Label Vector:
Labels present
Labels absent
8
Σ cpt C
Σ m & C.
(4) = P Σ
Cp + m &
A
Σ C
(5)
Con 7m
CPEYP
HRR XML Loss: We now have the output of our network and target vector that exist in a d' & T. dimensional space. A straightforward idea would be to take an embedding style approach to make the loss function {(x, = ss & a|[2- This intuitive and matches prior approaches to XMI. 128 30 However, we found that such an approach resulted in no learning and degenerate random- guesssng performance. This 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 é. Because binding many values in fixed dimension d' 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 for the same components we would expect to find in the true label s. We remind the reader that we can query if class Cp by checking
s 1. We normalize this dot product, i.e., use the cosine similarity cos(s, <))) = || to perform these queries 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.
5

---

With the bounded cosine response, our loss has two components. First we build a loss term that goes though all present labels )", checking that each can be extracted. This involves computing p @ S to extract the symbolic statement representing all present vectors (i.e., p 69 S ~ Le,ey" Cp). Then we use each label HRR vector cp and check if it is present in the extracted output. This results in eq.
Next we confirm that the absent labels (the vast majority) are not queryable from the output. Rather than enumerate all L | 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 eq. 7
J/- - E cos (p' cp)) CrEYN
(6)
Jn cos
m' 2 S,
Σg Cp CPEYD
This negative component of the loss works because it is minimized by having the absent labels m @ 8 and present labels Ec,gyr 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 d' << L dimensions and ((D?)) time. The final loss is simply {(,, 8) = Jp + Jn.
We remind the reader that the target label s is present in the form of knowing the exact cp E y vectors to use. One could. if preferred, denote this loss as 8() 8). We also note that expectation may be that a new hyper-parameter À is needed to balance between the relative importance of eq. ( and eq. 7 However, we find that no such parameter is needed and simply adding them together is effective.
Experiments & Analysis
We will now conduct experimental evaluation of new HRR based approach XML classifica- tion. We emphasize to the reader that this is to show that the HRR approach of symbolically modeling goal, and then back-prop 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 simply a task we are applying the HRR to show the pros (and some cons) of the HRR ap- proach. 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 provide Each will be endowed with our HRR dense label representations as described in $ Jusing our improved HRR initialization from $ (becoming HRR-FC, HRR- and HRR-LSTM The CNN & LSTT are taken from the XML-CNN K51 and AttentionXML
A1 works. The AttentionXMLL 's hierarchical prediction head is replaced with 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 & vectors, well as the label vectors Cp. impact of increasing the HRR dimension d', 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- random-guessing performance, and thus will not be explicitly included in results.
5.1 Datasets & Evaluation Metrics
To assess the impact of dense label representations, we use eight of the datasets from Bhatia et al. 44. Table
T (see appendix) provides statistics about each dataset used for experiments. The average number of samples per label varies from 2.29-112999 1902.15. and the average number of labels per data point varies from 2.40-75.54. Bhatia al. 4 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
We did contact 44 for all text data but received no reply.

---

labels. The features are bag-of-worde 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- pre-proceseed 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 metries in our evaluation that are common in XML work, Precision at A (P@@ k) and the propensity score at k (PSP@k). k). Given rank, (y) as the rank of all the labels in y and pt the relative frequency of the I'th label, the P@k k (Equation 8) measures raw predictive accuracy of the top-k guesses, and PSP @ (Equation 9) down-weight correctly predicting frequent classes counteract the power-law distribution of labels common XML problems.
P@k
Σ Y1
(8)
PSP
Σ
y1
Pr
(S)
IErank, (S)
For brevity we will focus on l == 1 in most experiments, but found that k E [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@ or PSP@k as to make them redundant.
5.2 Network Architectures
The baseline multi-label network is fully-connected (FC) network with two hidden layers. Both hidden layers have the same size of 512 with ReLU activation. The basline network has I. 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 512x d'' where d' 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 has the same architecture
their code is used as the baseline, and our modified version 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 approach used for the output prediction of AttentionXML involved in a hierarchical sequence of fully connected layers applied per output token to produce a single scalar output, which makes it non-viable directly convert to an HRR based approach. For this reason we replace the final hierarchical prediction heads of AttentionXMI with the same attention mechanism but use standard fully-connected output layer like the FC and XML-CN EML-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.
The
Our goal is not to determine the most accurate possible XML model, and for this reason we do not perform any expensive hyper-paramette search over the architectures for any of the six models con- sidered (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 [5 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 isolate the HRR's 's impact, and intrinsically puts the HRR network at disadvantage because it has fewer parameters.
5.3 XML HRR Accuracy
We first investigate how the smaller HRR space of d' < L dimensions impacts each model's accuracy. Table shows the performance of HRR approach to its respective baselines, evaluated at k for brevity. For all datasets, dimension size d is 400 except in case of Amazon- Wikil0-31K.
7

---

Delicious-2000 and Amazon-670K where is 3000. In many cases our HRR based model approaches the high accuracies of -fate-of-the-ar 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 denote being within 5% (relative) of scores reported by 135 and for 5% of the original AttentionXML
Table 1: Accuracy of our baseline models and their HRR counterparts with the same network architecture otherwise. Cases where the HRR outperforms its baseline counterpart are in bold.
Bibtex
Delicious
Mediamil
Amazon 12K
Model
FC
HRR-FC
FC
HRR-FC
FC
HRR-FC
CNN
HRR-CNN
P@1
46.4
60.3
65.0
66.5
84.8
83.9
89.1
84.5
PSP@1
32,5
45.6
64.2
30.0
64.2
63.7
49.2
44.2
EURLex-4K
Amazon- 133
Model P@
FC
HRR-FC
CNN
HRR-CNN
LSTM
HRR-LSTM
FC
HRR-FC
73.4
77.2 30.7
47.1
50.0
70.4
93.0a
93.3
PSP@
32.0
18.0
17.5
26.4
26.8
52.6
49.6
Wiki10-31K
Amazon- 133
Model
FC
HRR-FC
CNN
HRR-CNN
L.TTM
HRR-LSTM
LSTM
HRR-LSTM
P@1 1
80.4
81.1
60.0
74.3
83.5
85.0
90.0
93.4
PSP@1 1
9.46
9.19
10.4
9.88
10.6
10.5
48.7
48.8
Delicious-200K
Amazon-670K
Model
FC
HRR-FC
FC
HRR-FC
CNN
HRR-CNN
P@1 1
21.8
44.9
34.6"
19.9
14.1
6.11
PSP@
10.5
6.84
5.22
8.45
9.39
1.51
Each bold case shows HRR improving over its baseline. HRR-FC Bibtex improved 1.30 - 1.40x and Delicious-200k: P@ improved 2.06 despite 1.52x decrease in PSP@ HRR-CNN improved the Wiki10-31K results by 1.24x. In most cases when the HRR results are not better, they are near the performance of the baseline. Most PSP@ show a S 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-free www-frequnncy labels, but often significantly better at high-frreqeene labels (a trade off that is task specific). The primary outlier in behavior is the Amazon-670K dataset, which appears be pushing the limits of the HRR approach's 's ability to distinguish between the 670K label vectors. While this is negative result in terms of XML, retrieve the correct label 19.9% of the time out of space of 670K labels a near three order of 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.
goal
improve HRRs: the ability predict
magnitude improvement
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 XML benchmarks. Similar results have been found systematic review & replication of work in information retrieval and triplet learning [47 but such investigation is beyond the scope of our work.
Table 2: For each dataset the percentage reduction in parameters of the output layer, and the resulting change for the entire network, by replacing the output layer from fully-connected softmax with our HRR approach.
5.4
HRR Model Compression & Runtime
Because of the size of the output space I., 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 the output layer by 59- 99%, which accounts for 29-42% of the model's total parameters in most cases. The mild ex- ception is the Amazon-133 13k corpus, which has a large number of input features and compar- atively smaller output space. This shows that
% Compression Output
Dataset
Dim d'
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

---

our HRR approach naturally provides more compact representation that could be applicable for situations with a high arity discrete outputs, yet allows learning continuous fashion without any sampling tricks.
Fewer parameters leads to a natural speedup in training time too. Table shows the optimization time for training epoch for a multi- label baseline and HRR-FC where we see an up-to 6.3x 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.
Table 3:
Speedup in training time for HRR-FC over the FC model. Bold indicates im- proved runtime.
Dataset
Speedup
Bibtex Delicious
0.35
0.38
Mediamill
0.39
EURLex-4K
0.35
We note that separate from the training time, 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 's output 8, but this need not be the case. There 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.
Wiki10-31K
1.48
Amazon-13K
1.33
Delicious-200K
4.47
Amazon-670K
6.28
5.5 Assessing Impact of Hyper-parameter
By demonstrating non non-trivial learning that can match or even improve upon the accuracy a standard fully-connected output layer that naturally leads to reductions in model size/memory 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 modification get consistent random-guessin performance across all datasets.
However, our larger goal is to gain new information about how to learn with HRRs. As such we now perform number of ablation experiments to elucidate potential factors relevant to future work outside of XMI.. This includes the impact of the output dimension d', 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 just the Wikil0-31K dataset in this section found it tracks well with overall behavior on other corpora.
Label Dimension Size: While training a model with dense label representation, the vector size d' of the label is fixed. Fig- ure 2 shows the impact of vector dimen- sion size on the model's precision. As ob-
60
Precision
40
Amaron-
served, Precision @5 increases when the dimension size is increased (and is repre- sentative of other metric's ' behavior). For datasets Wikilo
20
Delicious- 200K
Amzzon-6700
0
1,000
2,000
3,000
4,000 5,000
and AmazonCat-13k the precision begins to plateau when the dimension size is approximately 10% of
Dimension size d'
Figure 2: P@5 (y-axis) performance quickly plateaus the output network size d' (x-axis) increases. The plateau occurs at d' < 10% L, requiring a smaller percentage of all labels L as L increases.
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 a dimension size of 2500, which is 1.25% of the number of labels. Thus, Figure Segure@sugee suggests that HRR substantially compress the size of the label vector 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 both models are made larger. Results from Wiki10-31K

---

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 d' can increase performance from the initial 53.2 53.25% up to 58.51 %. All these HRR-FCss still have fewer parameters than the initial baseline network.
Table 4: Increasing the number of layers or hidden neurons has less benefit to the FC base- line compared to the HRR approach.
Net.
Layers
Hidden h
Out d'
P@5
2
512
30938
46.64
2
2048
30938
47.91
FC
512
30938
41.92
3
2048
30938
45.25
Updating p & m Vectors: The p and m vectors are the key to the cumulative positive and negative class vectors. is possible 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 (d' < 400). As d' increases we observe impact from learning the values of p and m. This was consistent across all datasets and architectures.
512
400
55.06
3 2048
400
55.36
HRR
3
2048
750
56.84
2048
1500
57.80
2048
3000
58.51
Updating Label Vectors Cp= Another question is if we should have allowed the label vectors Cp to altered dur- ing training, rather than holding them fixed at initialized values. We test this Table 3Jusing a network with mul- tiple different numbers of hidden neurons h and output dimensions d' for a 2-layer network, where the Vc, is the performance when we allow the concept vectors to be learned. We note that this was implemented by always pack-propagating through our complex unit magnitude projection т,, and resulted no significant performance difference. Experiments without the projection æ had significantly degraded results that gave random- guuessig performance.
Table 5:
Ablation test of whether la- bel vectors Cp should be altered during training (right most column) or remain fixed (2nd from right). Results are from Wiki10-31k as a representative dataset.
P@5
Hidden
Out d'
Fixed
V cp
512
400
55.06
53,50
2048
400
55.36
55,45
2048
750
56.84
56.75
2048
15500
57.80
57.69
2048
3000
58.51
58.18
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 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 the HRR concept vectors redundant. Further exploration of this is needed in future studies.
6 Conclusion
We have improved the initialization of HRRs to increase binding and retrieval accuracy, allowing for a convenient & differentiable ncuro-symbolic approach. To demonstrate potential utility we have applied HRRs to extreme multi-label classification. We observe reduced model size, faster training, and tabbe-to-improved accuracy. This provides evidence for the general utility and further study of HRRs. The learning dynamics of HRRs not yet fully understood by work and have the counter-intuine intuitive behavior that learning with them, but not altering them, tends to have the best results. Compared to prior works looking HRRs have significantly improved the viability of building more complex networks that leverage the symbolic manipulation properties of HRRs, which opens the door to new kind of approach modeling problems.
References
[1] Plate, "Holographic reduced representations," IEEE Transactions on Neural Networks, vol. no. 3, pp. 623-641, 5 1995. [Online). Available: http://wwwppp.r..e..eeooddoooo/e
[2] Smolensky, "Tensor product variable binding and the representation symbolic structures in connectionist systems," Artificial Intelligence, vol. 46, no. 1, pp. 159-216, 1990. [Online].
10

---

[3] K. Greff, S. van Steenkiste, and J. Schmidhuber, "On the binding problem in artificial neural networks," " arXiv, 2020. [Online]. Available: http://axxiv.org//b///21112222
[4] I. Schlag, K. Irie, and Schmidhuber, "Linear transformers are secretly fast weight programmers," in Proceedings of the 38th International Conference on Machine Learning. ser. Proceedings of Machine Learning Research, M. Meila and T. Zhang, Eds., vol. 139. PMLR, 2021, pp. 9355-9366 [Online]. Available: http::/proceedings. mlr. press/v wwt.sssrs....r.s..e........r 133/schlag22a..mmm
[5] Q. Huang, P. Smolensky, X. He, I.. Deng, and D. Wu, "Tensor product generation networks for deep nlp modeling," in Proceedings of the 2018 Conference of the North American Chapter of the Association for Computational Linguistics: Human Language Technologies, Volume I (Long Papers). Association for Computational Linguistics, jun 2018, pp. 1263-1273, [Online]. Available: https://cclanboology org/N18-11114
[6] I. Schlag and J. Schmidhuber, "Learning ucts," in Advances in Neural Information Processing Systems, vol. 31. Curran Associates, Inc., 2018. [Online]. Available: http::/ppeceedin......rrcccppp/p mecurips.co/papr//211///i
with third order tensor prod-
[7] K. Schlegel. P. Neubert, and P. Protzel, "A comparison of vector symbolic architectures," arXiv, 2020. [Online]. Available: http:://rxiv.orrr///... wttp:/bbbb//00.1119977
[8] M. Imani, D. Kong, A. Rahimi, and T. Rosing, "Voicehd: Hyperdimensional computing for efficient speech recognition." in 2017 IEEE International Conference on Rebooting Computing (ICRC). IEEE, nov 2017, pp. 1-8. [Online]. Available:
www.://wwe..eeeeoeeduuuueeeeeeee 1236ee/ 123650/
[9] P. Neubert, S. Schubert, and P. Protzel, "Learning vector symbolic architectures for reactive robot behaviours," in Proc. of Intl. Conf. Intelligent Robots and Systems (IROS) Workshop Machine Learning Methods for High-Level Cognitive Capabilitiess in Robotics, 2016. [Online]. Available: https://www.ii https:/www.uu-chemmni.. httpeemmiii.eeettttataaatiiiiiie nnwuurtr
[10] M. N. Jones and D. J. Mewhort, "Representing word meaning and order information in composite holographic lexicon," Psychological Review, vol. 114, no. 1, pp. 1-37, 2007.
[11] P. Blouw and C. Eliasmith, "A neurally plausible encoding of word order information into a semantic vector space," " 35th Annual Conference of the Cognitive Science Society, vol. 35, pp. 1905-1910, 2013.
[12] T. C. Stewart and C. Eliasmith, "Large-scale synthesis of functional spiking neural circuits," Proceedings of the IEEE, vol. 102, no. 5, pp. 881-898, 2014.
[13] Blouw, E. Solodkin, P. Thagard, and C. Eliasmith, "Concepts semantic pointers: A framework and computational model." Cognitive Science, vol. 40, no. 5, pp. 1128-1162. 7 2016. [Online]. Available: http:///oi.wwieee www.wwwwwwo////...
wwt.:/cmmooo.o 10. 1t..m//0..11//ogss.... 12265
[14] C. Eliasmith, C. Stewart, X. Choo, T. Bekolay, DeWolf, Y. Tang, and D. Rasmussen, "A
large-scale model of the functioning brain," Science, vol. 338, no. 6111, pp. 1202- 1205, 11 2012. [Online]. Available: https://www.sccennee. wwwp://ewemm...ge/ooo/o/r///ep/e wttp://ooooo...111....101 126/science..... 1225266 1225526
[15] R. Singh and Eliasmith, "Higher-dimensions neurons explain the tuning and dynamics of working memory cells." Journal of Neuroscience, vol. 26, no. 14, pp. 3667-3678, 2006. [Online]. Available: https::/www. www.osjjeurosi..rrgg. wwtp.c/oooee//22//4/36666
[16] T. Bekolay. J. Bergstra, E. Hunsberger, WeWolf, T. Stewart, D. Rasmussen, X. Choo, A. Voelker, and C. Fliasmith, "Nengo: python tool for building large-scale functional brain models," Frontiers in Neuroinformatics, vol. 7, p. 48, 2014. [Online]. Available:
[17] M. Nickel, L. Rosasco, and T. Poggio, "Holographic embeddings of knowledge graphs," in Proceedings of the Thirtieth AAAI Conference on Artificial Intelligence, ser. AAAI'1.. AAAI Press, 2016, p. 1955-1961.
11

---

[18] S. Liao and B. Yuan, "Cireconv: A structured convolution with low complexity." in Proceedings of the AAAI Conference on Artificial Intelligence. vol. 33, 2019. pp. 4287-4294, [Online]. Available:
[19] I. Danihelka, G. Wayne, B. Uria, N. Kalchbrenner, and A. Graves, "Associative long short-term memory," in Proceedings of The 33rd International Conference on Machine Learning. 2016, pp. 1986-1994.
[20] S. Badreddine, A. d. Garcez, L. Serafini, and M. Spranger, "Logic tensor networks," arXiv, pp- 1-70, 2020. [Online]. Available:
[21] Mao, C. Gan, P. Kohli, B. Tenenbaum, and J. Wu, "The neuro-symbolic concept learner: In- terpreting scenes, words, and sentences from natural supervision," 7th International Conference on Learning Representations, ICLR 2019, pp. 1-28, 2019.
[22] L. Serafini and A. D. Garcez, "Logic tensor networks: Deep learning and logical reasoning from data and knowledge," CEUR Workshop Proceedings, vol. 1768, 2016.
[23] W. Bi and J. Kwok, "Efficient multi-label classification with many labels," in ICML, ser. Proceedings of Machine Learning Research, S. Dasgupta and D. McAllester, Eds., vol. 28, no. 3. Atlanta, Georgia, USA: PMLR, 2013, pp. 405-413. [Online]. Available: http://proceedinss..lr press///ssss//221l.l.. http://o
[24] H. Jain, Y. Prabhu, and M. Varma, "Extreme multi-label loss functions for recommendation, tagging, ranking &amp: other missing label applications." in Proceedings of the 22nd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ser. KDD 116. New York, NY. USA: Association for Computing Machinery, 2016, p. 944.944. [Online]. Available: http://0o..org/00004445999999222
[25] Y. Prabhu and M. Varma, "Fastxml: A fast, accurate and stable tree-classifier for extreme multi-label learning," in Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ser. KDD '14. New York, NY. USA: Association for Computing Machinery, 2014, p. 263-272. [Online]. Available: http://db.or///11111422223333333
[26] J. Weston, A. Makadia, and H. Yee, "Label partitioning for sublinear ranking," in ICML, ser. Proceedings of Machine Learning Research, S. Dasgupta and D. McAllester, Eds., vol. 28, no. 2. Atlanta, Georgia, USA: PMLR, 2013, pp. 181-189, [Online]. Available: http://wweeddd.....mreeeee////vs
[27] W. Siblini, P. Kuntz, and F. Meyer, "Craftml, an efficient clustering-basee based random forest for extreme multi-label learning." in ICML, ser. Proceedings of Machine Learning Research, Dy and A. Krause, Eds., vol. 80. Stockholmsmässan, Stockholm Sweden: PMLR, 2018, pp. 4664 4673. [Online). Available: http://pooceddings...pppeess/s/e pres. 18a.
[28] A. Jalan and P. Kar, "Accelerating extreme classification via adaptive feature agglomeration," in Proceedings of the Twenty-Eight International Joint Conference on Artificial Intelligence. California: International Joint Conferences on Artificial Intelligence Organization, 8 2019, pp. 2600-2606. [Online]. Available: https://www.jjcal www.:iaaww.rg/ooccccinnn///////a
[29] Y. Tagami, "Annexml: Approximate nearest neighbor search for extreme multi-label classification." in Proceedings of the 23rd ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, ser. KDD '17. New York, NY, USA: Association for Computing Machinery, 2017, p. 455-464. [Online]. Available: 1ttpoo/org/...11/3/7793333...000
[30] K. Bhatia, H. Jain, P. Kar. M. Varma, and P. Jain, "Sparse local embeddings for extreme Advances in Neural Information Processing Systems 28, C. Cortes, N. D. Lawrence, D. D. Lee, M. Sugiyama, and R. Garnett, Eds. Curran Associates, Inc., 2015, pp. 730-738. [Online]. Available:
multi-label classification."
for- eor-extreme- multi- label- classsssssssciiioo..ddd
12

---

[31] H.-F. Yu, P. Jain, P. Kar, and I. S. Dhillon, "Large-scale multi-labe learning with missing labels." in Proceedings of the 31 International Conference on International Conference on Machine Learning- Volume 32, ser. ICMI'14. JMLR.org, 2014, p. 1-593-1-601.
[32] A. Niculescu-Mizil and E. Abbasnejad, "Label filters for large scale multilabel classification," " in Proceedings of the 20th International Conference on Artificial Intelligence and Statistics, ser. Proceedings of Machine Learning Research, A. Singh and J. Zhu, Eds., vol. 54. Fort Lauderdale, FL. USA: PMLR, 2017, pp. 1448-1457, [Online]. Available: http://proceedingg.mmm mlr, press/v54/miculescn http://icculecuuuuiililll (aa.amiiiiiiilliiiiii html
[33] H. Jain, V. Balasubramanian, B. Chunduri, and M. Varma, "Slice: Scalable linear extreme classifiers trained on 100 million labels for related searches," in Proceedings of the Twelfth ACM International Conference on Web Search and Data Mining, ser. WSDM '19. New York, NY, USA: Association for Computing Machinery, 2019, p. 528-536. [Online]. Available:
https///oi.orr// 1O. 145/328900032290000
[34] R. Babbar and B. Schölkopf. "Dismec:
Distributed sparse machines for extreme multi-label classification," in Proceedings of the Tenth ACM International Conference Web Search and Data Mining, ser. WSDM '17. New York, NY, USA: Association for Computing Machinery, 2017, p. 721-729. [Online]. Available: https::/doi..rr// 01511000111/01111100000001
[35] J. Liu, W.-C. Chang, Y. Wu, and Y. Yang, "Deep learning for extreme multi-label text classification," in Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, ser. SIGIR '17. New York, NY, USA: Association for Computing Machinery, 2017, p. 115-124. [Online]. Available: http://d00.rg/110111555/77777771
[36] T. Jiang, D. Wang, L. Sun. H. Yang, Z. Zhao, and F. Zhuang, "Lightxml: Transformer with dynamic negative sampling for perfooreform extreme multi-label text classification,"" " in AAAI, 2021. [Online]. Available: http://arxii.. wtwpsxii.org/bb//1111111 00300
[37] K. Dahiya, D. Saini, A. Mittal, A. Shaw, K. Dave, A. Soni, H. Jain, S. Agarwal, and M. Varma, "Deepxml: A deep extreme multi-label learning framework applied to short text documents," in Proceedings of the 14th ACM International Conference on Web Search and Data Mining, ser. WSDM '21. New York, NY, USA: Association for Computing Machinery, 2021, p. 31-39. [Online]. Available: https://doi.
34441810
[38] A. Mittal, K. Dahiya, S. Agrawal, D. Saini, S. Agarwal, P. Kar, and M. Varma, "Decaf: Deep extreme classification with label features," in Proceedings of the 14th ACM International Conference on Web Search and Data Mining, ser. WSDM '21. New York, NY, USA: Association for Computing Machinery, 2021, p. 49-57. [Online]. Available: htps://doi.org/10. 145/4437963.3441555
[39] W.-C. Chang, H.-F. Yu, K. Zhong, Y. Yang, and I. S. Dhillon, "Taming pretrained transformers for extreme multi-label text classification," in Proceedings of the 26th ACM SIGKDD International Conference on Knowledge Discovery &amp; Data Mining, ser. KDD '20. [Online].
New York, NY. USA: Association for Computing Machinery, 2020, p. Available:
[40] T. K. R. Medini, Q. Huang. Y. Wang, V. Mohan, and A. Shrivastava, "Extreme classification in log memory using count-min sketch: A case study of amazon search with 50m products," in Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. ditetqquotsiingle Alché-Buc, E. Fox, and R. Garnett, Eds., vol. 32. Curran Associates, Inc., 2019. [Online]. Available: |httss Vproceedinggs.cumme http://wwww.p..e.eooooooooooooo.
[41] R. You, Z. Zhang, Z. Wang. S. Dai, H. Mamitsuka, and S. Zhu, "Attentionxml: Label tree-based attention-aware deep model for hegh-performance extreme multi- label text classification," in Advances in Neural Information Processing Systems 32, H. Wallach, H. Larochelle, A. Beygelzimer, F. dttettuuotesingle Alché-Bue, E. Fox, and R. Garnett, Eds. Curran Associates, Inc., 2019, pp. 5820-5830. [Online]. Available: http://eeeeettttotooooottotttott
label- www.-e--aaaeeddattetto----aaaaaa attention-aware
13

---

[42] C. Guo, A. Mousavi, X. Wu, D. N. Holtmann-Rice S. Kale, S. Reddi, and S. Kumar, "Breaking the glass ceiling for embedding- classifiers for large output spaces," " in Advances in Neural Information Processing Systems, H. Wallach, H. Larochelle, A. Beygelzimer, F. ditextquotesingle Alché-Buc, E. Fox, and Garnett, Eds., vol. 32. Curran Associates, Inc., 2019. [Online]. Available:
7817696ea21ccac35a775333 25t.
[43] M. Wydmuch, K. Jasinska, M. Kuznetsov, R. Busa- Busa-Fekete, and K. Dembezynski, "A no-regret generalization of hierarchical softmax to extreme multi-label classification," in Advances in Neural Information Processing Systems, 2018, pp. 6355-6366.
[44] K. Bhatia, K. Dahiya, Jain, A. Mittal, Y. Prabhu, and M. Varma, "The extreme classification repository: Multi-label datasets and code," 2016. [Online]. Available: http://mamikvarmma http://amilkarmma.ordddooooooddo
[45] X. Bouthillier, P. Delaunay, M. Bronzi, A. Trofimov, B. Nichyporuk, J. Szeto, N. Sepah, E. Raff, K. Madan, V. Voleti, S. E. Kahou, V. Michalski, D. Serdyuk, T. Arbel, C. Pal, G. Varoquaux, and P. Vincent, "Accounting for variance in machine learning benchmarks," in Machine Learning and Systems (MLSys), 2021. [Online]. Available:
[46] X. Bouthillier, C. Laurent, and P. Vincent, "Unreprodueible research is reproducible," in Proceedings of the 36th International Conference on Machine Learning, ser. Proceedings of Machine Learning Research, K. Chaudhuri and R. Salakhutdinov, Eds., vol. 97. Long Beach, California, USA: PMLR, 2019, pp. 725-734. [Online]. Available: http://rroceedings.uu ptw.s////...eee////o/llllllle.e. 19.html
[47] M. F. Dacrema, P. Cremonesi, and D. Jannach, "Are really making much progress? a worrying analysis of recent neural recommendation approaches," in Proceedings of the 13th ACM Conference on Recommender Systems RecSys '19. New York, New York, USA: ACM Press, 2019, pp. 101-109. [Online]. Available:
http://dl. http://aatoo..cmmooodd3333393930
[48] K. Musgrave, S. Belongie, and S.-N. Lim, "A metric learning reality check," in ECCV, 2020. [Online]. Available: http:://rxiv.org////// http://iiw...rr/bb/20000....0.00
[49] R. Gayler, "Multiplicative binding, representation operators & analogy," in Advances in analogy research: Integr. oftheory and data from the cogn., comp., and neural sciences, 1998.
[50] Gosmann and C. Eliasmith, "Vector-derived transformation binding: An improved binding operation for deep symbol-like processing in neural networks," Neural Comput., vol. 31, no. 5, pp. 849-869, 5 2019. [Online]. Available: https:///oii org/ I0. 1162/neco. a 01179
[51] E. P. Frady, D. Kleyko, and T. Sommer, "A theory of sequence indexing and working memory in recurrent neural networks," Neural Computation, vol. 30, no. 6, pp. 1449-1513, 2018
[52] C. G. Snoek, M. Worring, J. C. Van Gemert, J.-M. Geusebroek, and A. W. Smeulders, "The chal- lenge problem for automated detection of 101 semantic concepts multimedia," " in Proceedings of the 14th ACM international conference on Multimedia, 2006, pp. 421-430.
[53] I. Katakis, G. Tsoumakas, and I. Vlahavas, "Multilabel text classification for automated tag suggestion," in Proceedings of the ECML/PKDDD, vol. 18, 2008 p. 5.
[54] G. Tsoumakas, I. Katakis, and Vlahavas, "Effective and efficient multilabel classification in domains with large number of labels." in Proc. ECML/PKDD 2008 Workshop on Mining Multidimensional Data (MMD'08), vol. 21, 2008, pp. 53-59.
[55] Leskovec and A. Krevl, "Snap datasets: Stanford large network dataset collection," 2014.
[56] A. Zubiaga, "Enhancing navigation on wikipedia with social tags," arXiv preprint arXiv: /20..4469 2012.
[57] J. McAuley and J. Leskovec, "Hidden factors and hidden topics: understanding rating dimen- sions with review text," in Proceedings of the 7th ACM conference on Recommender systems, 2013, pp. 165-172.
14

---

[58] R. Wetzker, C. Zimmermann, and C. Bauckhage. "Analyzing social bookmarking systems: A del. icio. us cookbook," Proceedings of the ECAI 2008 Mining Social Data Workshop. 2008, pp. 26-30.
[59] C. Luo and A. Shrivastava, "SSH (sketch, shingle, & hash) for indexing massive-scale time series," " Proceedings of the Time Series Workshop at NIPS 2016, ser. Proceedings of Machine Learning Research, O. Anava, A. Khaleghi, M. Cuturi. V. Kuznetsov, and A. Rakhlin, Eds., vol. 55. Barcelona, Spain: PMLR, 2017, pp. 38-58. [Online]. Available: http://proceedings..bb mir. press//55//uul16..tm http://pcedcaas..sppppsss//////a
[60] R. Pratap, "Efficient dimensionality reduction for sparse binary data," in IEEE Big Data, 2018, pp. 152-157.
[61] J. Liu, W.-C. Chang. Y. Wu, and Y. Yang, "Deep learning for extreme multi-label text classi- fication," in Proceedings of the 40th International ACM SIGIR Conference on Research and Development in Information Retrieval, 2017, pp. 115-124.
15


Reviews:
[{"review_id": "iWY2cmkt7a", "reviewer": "Reviewer_LW6b", "summary": "The paper makes an incremental change to an early cognitive model of symbol binding which positions the work in the context of other end-to-end neurosymbolic approaches that make use of embeddings.  ", "questions": "", "limitations": "", "rating": 6, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Without further evaluation either theoretical or through comparative experimental evaluations of the benefits of the proposed increment wrt the related work in this area, I don't believe that the paper can be accepted.\nHaving double checked the supplementary materials and the experimental results, I now appreciate the potential of the approach despite the lack of comparative evaluation results. I have increased my score accordingly.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "n/a", "review_text": "", "extra_scores": {"ethical_concerns": "n/a", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}, {"review_id": "XGet0z31ohB", "reviewer": "Reviewer_m8WY", "summary": "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.\n", "questions": "", "limitations": "", "rating": 7, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Update:\nThank you for your response. Given the clear responses to all reviewers, and given the discussion of significance with reviewers rafZ and sKB5, I will raise my score to a 7.\n--------\n\nSignificance: I will start my review by saying that I was previously unfamiliar with holographic reduced representations (HRRs), so it’s difficult for me to judge significance of improving learning in HRRs, and I will defer to the other reviewers as to the value of such a contribution. However, I think this paper does a very good job clearly stating the intended scope (“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.”), and I believe that these goals are fulfilled by the very thorough experiments. I think the authors do a good job showing improvements in HRR learning, exploring the pros and cons of HRRs, and that this technique could potentially be the basis for future work.\n\n\nClarity:  I found section 3 a bit confusing to read. In particular, I don’t think it was a self-contained introduction to HRRs for a reader who is unfamiliar. I would recommend first stating the intended high-level goals of the HRR approach, then showing an example of usage, and then discussing details such as the implementation and properties  (equations 1 and 2).\nAs a reader, it would be much more helpful to first read about the motivation of HRRs  (disused somewhat starting on line 104), before reading about how they are implemented (lines 93 - 103). \n\n\nOn the other hand, the experiments section (Sec 5) is very clearly written and easy to follow. I appreciate the clarity of this section. All experiments were clearly explained and the experimentation was thorough, comparing to FC, CNN and LSTM baselines (5.1) , examining the impact of hyperparameters (5.3), as well as discussing factors impacting runtime and how they could be improved (5.2). For a paper exploring the performance and behavior of a new technique, I think this work does a good job a) clearly explaining each experiment, b) thoroughly exploring different aspects which contribute to the performance of the new technique, and c) discussing other important considerations (such as runtime)\n\n\nAs I am not very familiar with HRRs, I will have to defer to other reviewers on the significance of the contribution, but I believe the quality of the evaluation is high, the evaluation section of the paper is thorough and clear, and the scope and claims of the work are clearly stated. For these reasons, I would tend to favor acceptance, provided that section 3 was rewritten to be a bit more clear.\n\n\nOther comments/questions:\n- It would be very helpful to show a figure with a concrete example of an XML task, so the reader can understand the task better.\n\n- What other domains/problems might HRRs be suitable for, besides XML? For somebody unfamiliar with HRRs, a discussion of other domains for future work would be very helpful to help give a sense of what future impact might be.\n\n\n\nThe paper does need a thorough proofread. Below are some minor notes and typos:\n- Line 191: what does the following sentence mean? “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.”\n- Table 1: it’s —> its (and other places throughout the paper)\n- line 225: to due to  —> in order to ?\n- line 110: sybmolic\n- line 226: Convoltuional\n- line 231: heiarchical\n- line 295: XXX lines of code — I assume this is meant to be replaced with an actual number?\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "No societal impact.\nAs discussed above, I think that the authors did a good job discussing the limitations of intended scope of their contribution.", "review_text": "", "extra_scores": {"ethical_concerns": "None.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "4"}, "extra_text": {}}, {"review_id": "NP8sAQNavak", "reviewer": "Reviewer_sKB5", "summary": "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.", "questions": "", "limitations": "", "rating": 8, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "Neural Networks struggle to generalise in systematic ways similar to humans. For this reason, there has been in recent years a push towards more systematic / neuro-symbolic representations in connectionist models. The binding problem is central in this research direction [1]. However, it is already known since the '90s how one may represent compositional/symbolic structures in a continuous vector space. These methods are sometimes also referred to as a Vector Symbolic Architecture (VSA).   Arguably the prototypical VSA is Smolensky's Tensor Product Representation (TPR) [2] but the need for a VSA with constant memory size independent of the complexity of the symbolic structure gave rise to many methods [3] among which HRR is a particularly early and popular one. However, as the authors correctly point out, connectionist models such as the HRR have not been combined with the powerful gradient descent based deep learning of today. It is for this reason that this work is so interesting: it gives compelling evidence and arguments for how HRRs can be employed as a representation inside a modern neural network that is trained by gradient descent on complex data. This comes with clear benefits compared to the TPR-based approaches of recent years published at top conferences (NeurIPS, ICML, ACL; see e.g. [4,5,6]). In addition, the paper is well written with a lengthy analysis. \n\n**Weaknesses**\n\n1.) VSAs with a constant size $d$, such as the HRR, eventually suffer from interferences if the number of bindings exceeds its capacity $m$.  In regular HRRs the capacity increases almost linearly with $d$ [7]. Unfortunately, a discussion on capacity is entirely missing from this work. \n\n\n**Questions**\n\n1.) What is the vector dimension for the HRR in figure 1? How large does the number of bound terms has to be in this case until the HRR fails? Maybe add this information to the figure description.\n\n2.) $1-\\text{cos}(p^* \\otimes \\hat{s}, c_p)$ is a logical choice but wouldn't it make also sense to use $\\text{exp}( \\langle p^* \\otimes \\hat{s}, c_p \\rangle)$ (where $\\otimes$ is the binding operator)? Modern binary Hopfield Networks (Classic Hopfield Networks can be thought of as TPRs) enjoy an increased capacity using an exponential energy function.\n\n3.) Similarly, $\\text{exp}(\\langle s, \\hat{s} \\rangle)$ would be an alternative objective function since it would have a better time complexity. I'd appreciate the authors' comment on this possibility. \n\n4.) After reading, it appears to me that the proposed method can directly be applied to large vocabulary language modelling problems like WikiText-103 (268k vocab) or the Google Billion Word benchmark (793k vocab)? This would be of great practical interest to the NLP research community. Have the authors considered this? The authors may find it useful to add such a possibility to their motivation or conclusion. \n\n**Comments**\n\ntypo on line 34, 110, 226, 231\n\nremove empty lines 103, 185\n\nbroken sentence on line 84-86\n\nforgotten placeholder on line 295\n\nrepetitive lines 88-91 and 221-224 can be removed since it is already stated in 35-37\n\n**References**\n\n[1] Greff, Klaus, Sjoerd van Steenkiste, and Jürgen Schmidhuber. \"On the binding problem in artificial neural networks.\" arXiv preprint arXiv:2012.05208 (2020).\n\n[2] Smolensky, Paul. \"Tensor product variable binding and the representation of symbolic structures in connectionist systems.\" Artificial intelligence 46.1-2 (1990): 159-216.\n\n[3] Schlegel, Kenny, Peer Neubert, and Peter Protzel. \"A comparison of vector symbolic architectures.\" arXiv preprint arXiv:2001.11797 (2020).\n\n[4] I. Schlag, J. Schmidhuber. Learning to Reason with Third Order Tensor Products. Advances in Neural Information Processing Systems (NeurIPS), Montreal, 2018. Preprint: arXiv:1811.12143\n\n[5] Qiuyuan Huang, Paul Smolensky, Xiaodong He, Li Deng, and Dapeng Wu. Tensor product generation networks for deep nlp modeling. In Proceedings of NAACL, 2018. URL https: //arxiv.org/abs/1709.09118.\n\n[6] I. Schlag, K. Irie, J. Schmidhuber. Linear Transformers Are Secretly Fast Weight Programmers. Proc. ICML 2021. Preprint: arXiv:2102.11174.\n\n[7] Plate, Tony A. \"Holographic reduced representations.\" IEEE Transactions on Neural networks 6.3 (1995): 623-641.\n\n\n---------------------------------------------\nUpdate:\n\nAfter discussion with the authors, I have decided to increase my score to an 8. ", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I have no suggestions for improvement.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "6"}, "extra_text": {}}, {"review_id": "MnTqXcvmZdn", "reviewer": "Reviewer_rafZ", "summary": "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.", "questions": "", "limitations": "", "rating": 7, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "[Summary and Contribution] The 90’s saw significant interest in “symbolic” approaches to AI. The basic idea of these techniques is to represent symbols as vectors and then to define operators that allow one to encode various relations between symbols. The primary benefit of such approaches, which are collectively known as “vector symbolic architectures” (VSA), is that they provide a structured way to encode complex relationships between objects into a single high-dimensional point. Tony Plate’s “Holographic Reduced Representation” (HRR) is one particular approach to this problem. These techniques subsequently fell out of vogue in the AI/ML community and were largely supplanted by neural networks trained using backpropagation. The primary contribution is a simple modification to the original approach of Plate that improves the storage capacity of HRR and leads to better accuracy when training in a neural network with backprop. The authors also present an interesting application of the technique to “extreme multi-label classification,” in which HRR essentially functions as a form of label compression, and show that it leads to results that are at least in the same ballpark as state-of-the-art techniques. While the contribution is fairly simple, this is an interesting piece of work connecting two different areas of AI and would likely be of interest to a fairly diverse audience of readers. The work additionally contains some useful practical guidance on that cannot be found elsewhere in the literature.\n\n[Originality] It is worth mentioning in the related work section that Plate himself discusses using HRRs with gradient based systems in his book “Holographic Reduced Representation” (see ch. 5 “Using Convolution Based Storage in Systems that Learn”). However, this work considers incorporating HRRs with additional types of network architecture and provides new insight into the choice of cost function. Additionally, there has been substantial work on using similar “connectionist” architectures in learning systems which warrants some brief discussion. See for example: Imani et. al “VoiceHD: Hyperdimensional computing for efficient speech recognition,” Kleyko et. al “Classification and recall with binary hyperdimensional computing: Tradeoffs in choice of density and mapping characteristics.” The work by Imani et. al also considers a combination of VSA representation and trainable neural network albeit in a very different way than is discussed here.\n[Quality/Clarity] This work is sound technically and is generally well written. I have the following comments:\n•\tIn general, the paper would be stronger if there was more formalism about what kinds of properties we need the HRRs to satisfy and some analysis of why they meet those requirements. In a nutshell, we need to be able to query the HRR to ask if a certain relation is present – it would be good to provide some brief description of the mathematics behind why HRRs are able to support this. For instance, on line 107, why should we expect that <S,cat> ~ 1 but <S,cow> ~ 0? A brief sketch of why this works out mathematically would be fine.\n•\tRelated to the above, it would be nice to provide some analysis of why the proposed modification improves query accuracy. There are several works that provide analysis of similar techniques and could be adapted to this setting. See for example, Frady et. al “A Theory of Sequence Indexing and Working Memory in Recurrent Neural Networks” or Thomas et. al “Theoretical Foundations of Hyperdimensional Computing” who both provide detailed analyses of related schemes.\n•\tThe choice of d (dimension of the HRR) seems fairly arbitrary here. The relationship between d, the number of relations to encode, and the probability of correctly answering a query has been characterized for several other related methods (see either of the two works referenced above). It would be good to provide some more formal guidance on how one should choose this parameter.\n•\tHRR is one particular instance of a broader family of methods for symbolic reasoning on vector representations – this line of work is often goes by the name “vector symbolic architectures” or “hyperdimensional computing.” Moreover, there are VSA architectures for which the “binding” operator (circular convolution here) is simpler computationally and has an exact inverse. I would have liked to see a bit of discussion as to why HRR might be preferred over other VSA architectures. A detailed discussion is probably beyond the scope here but it would be nice to at least discuss this question a bit and point the reader to some of the other literature in this field.\n•\tMinor comments/Typos:\no\tThe requirement that the embeddings be sampled from a N(0,1/d) distribution is sufficient, but not necessary.\no\tLine 85 “is high architecture” – line 94 “it’s” – line 154 “response tightly” – line 225 “HRR to due to show” – line 295 “implemented with XXX lines of code – line 316 “the largeness of” – line 341 “is queries against”\n[Significance] This work represents an important first step in bringing classic work on connectionist/symbolic AI into the fold of modern machine learning. The connectionist approach has a lot of interesting qualities and has recently seen a resurgence of interest from the hardware community, who have made extensive use of such techniques to offer low-power alternatives to conventional ML algorithms like SVMs and MLPs. However, these techniques are under-studied by the main-stream ML community and their utility for solving complex learning tasks remains unclear. This work provides novel and useful practical guidance and will likely spur greater interest in this area by other ML researchers. From that perspective, the authors may want to provide a bit more discussion as to why HRR/VSAs are a promising direction in general and warrant further attention. What do these techniques offer that conventional approaches based on deep neural networks alone do not? On the other hand, do these methods have clear limitations? What do DNNs offer HRRs? Are there reasons to prefer HRRs over other methods for label compression? These questions are all speculative, but offering some opinions on them would generate good material for future discussion. \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "This work is fairly agnostic with respect to applications and beyond the possible societal impacts that are inherent in any work about developing better classification algorithms I see no particular causes for concern about this work. I do not think any further action on the part of the authors is required.", "review_text": "", "extra_scores": {"ethical_concerns": "As noted above, I see no particular ethical concerns beyond those present in any AI research. ", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper revisits the use of Holographic Reduced Representation (HRR) as a way to combine symbolic reasoning with a neural system. It proposes a new method to efficiently train HRRs. The authors demonstrate that replacing a traditional output layer of a network with a semantically meaningful HRR layer is very effective, in terms of drastically reducing the output layer size and also reducing the overall network size. The results suggest that this is a promising approach that will likely spark future work.

The paper led to substantial discussion among the reviewers and authors, and the authors' informative clarifications helped make all reviewers much more confident in the accuracy and value of the work.

With the authors incorporating their insightful replies into the final version of the paper, this will make a solid NeurIPS paper with fairly broad interest.
Decision: Accept (Spotlight)