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 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 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-symboie. 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 & 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-1129990 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
63.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. 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 be 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:///wwwwwoeeeee..rrroo//o/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.or//ab///211222
[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 neurrpps.c/paper/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/000.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.eeettttatatttiiiiiie newpo/tt
[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.:/cmmmoooo 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://ewemmn..geoooo/o/r///ep/e wttp://ooooo...111....101 126/science..... 1225266 1225526
[15] R. Singh and Eliasmith, "Higher-dimensionn neurons explain the tuning and dynamics of working memory cells." Journal of Neuroscience, vol. 26, no. 14, pp. 3667-3678, 2006. [Online]. Available: httpp::/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///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.r..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..rr// 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// 1151110111100000111100000
[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//10111555/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 wwwpeeeddings..uuriiss..oo 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.-r--aaaeeddattetton---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.oroddooooooddo
[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. 99.htll
[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.orgg///// 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": "X331kVXXlaP", "reviewer": "Reviewer_M8pZ", "summary": "This paper presents a modification to the HRR along with a novel loss that permits efficient learning in large output spaces. The approach is demonstrated on a number of extreme classification tasks and this appears to be the first work that shows the possibility of backpropagating through HRRs that bind many elements.\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": "This paper presents a modification to the Holographic Reduced Representation that increases the precision of the unbinding operator while maintaining numerical stability and avoiding costly cleanup operations. The paper also presents a novel loss that supports learning in large label spaces. Together, these are applied to extreme classification using an approach that relies on two fixed, orthogonal, role vectors (label present / not present) and many label fillers. This approach supports the novel loss that considers all of the labels without iterating over the large label space, by checking that absent labels are not bound to the label-present role. For extreme classification tasks where few labels are present at any one time, this is significantly more efficient in terms of time and parameters than methods that explicitly model the entire label space.\n\nResults are presented for a number of extreme classification benchmarks, and the new approach is compared to equivalent models that replace the HRR output layer with a standard logistic layer. These results show that the loss is working well and being backpropagated through theeffectively through the (fixed) HRR. There is a discussion of the effect of learning both the role and filler representations but this doesn't seem to have a big effect on the tasks studied.\n\nOverall, I think this is a nice contribution with an interesting set of results. The paper would be even stronger with more discussion of how these results could extend to tasks beyond the current classification settings, that may more explicitly require the binding and unbinding operations made available by the HRR.\n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The application to extreme classification demonstrates the approach's ability to represent, and learn in, large label spaces. But it only models two roles (label present / not present) and does not investigate the HRRs ability to represent diverse role-filler combinations, or even recursive structures, in a fixed size representation. The paper would be stronger with a discussion of how these results could extend to other applications of the HRR that test its ability to bind arguments in more challenging ways.\n\nWhile there hasn't been much recent work on learning with HRRs. There has been a line of recent work focused on learning with the very related Tensor Product Representation. I think that work should be mentioned in this paper.\n", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}, {"review_id": "HY4-ItaKugS", "reviewer": "Reviewer_rRrp", "summary": "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. \nused for approximating symbolic storage and retrieval operations.\n\nThe 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.\n\nThe 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.\n\nThe 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.)", "questions": "", "limitations": "", "rating": 6, "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": "*Strengths (soundness; theoretical grounding; empirical evaluation; significance and novelty; relevance to NeurIPS community)*:\n- Novelty of the proposed operation. The authors introduce a projection scheme to the original HRR operation in Plate 1995 and a means of incorporating HRR into modern learnable architectures that appears to be novel (though I am not an expert on the related work, and am comparing relative to the provided related works.) The projection modification seems to significantly improve the viability of the HRR operator over its original form -- it increases the query accuracy for the retrieval task. The usage of HRR operations in a learnable framework at all appears novel.\n- Practical contribution: the authors convincingly demonstrate that the HRR operation allows a useful task (queryable lookup and retrieval of many labels in a low-dimensional vector) to be performed efficiently and relatively accurately with fewer vector parameters. \n- The empirical evaluations on the XML task use real-world datasets and demonstrate comparable (and in some cases SOTA-exceeding) performance over a fully-connected baseline for the lookup task, using several different neural architectures (FC; CNN; LSTM) as the base with the HRR layer as the final layer.\t\n- Significance and potential relevance. The introduction and empirical task certainly suggest that the operation could be a useful new operation in the neural toolkit that can emulate important symbolic operations. However, I believe this aspect can be clarified and tightened, as discussed next. \n\n\n\n*Weaknesses (soundness; theoretical grounding; empirical evaluation; significance and novelty; relevance to NeurIPS community)* :\n- Paper framing and next steps using the HRR operation. While reading this paper, I found myself confused about what the goals of this paper were, which would determine the appropriate metrics for evaluating whether the proposed model had or had not succeeded, and what its prospects were as a significant new tool in vector-based computation. While the authors introduce a reasonably novel operation (the HRR framework) and provide proof-of-concept empirical evaluations demonstrating that it is viable on a practical XML task, they stop short of (and in fact explicitly say) that their goals are not to demonstrate state-of-the art XML performance. This is fine, but I believe a useful revision of this paper could paint a clearer and more precise picture of why the HRR operation is being introduced -- and what its clearest advantages are (or could be) over other approaches. The framing and goals of introducing HRR seem to change or are hard to pin down throughout the paper -- I think the introduction could benefit from a revision that crisply enumerates its advantages over other related methods (and the kinds of currently-neural operations it might be comparable to or seek replace). \n\nAt times the authors suggest that a major goal is to improve on HRRs (eg. L306-309) . This would make sense if a focus of the paper was for neurally-plausible cognition or tackling the other cognitive tasks (but it does not seem to be.) Otherwise, it would seem that a better focus would be on how HRR itself improves over the existing symbolic and neural SOTA toolkit early on (eg. the possibility of distillation; improved accuracy on other kinds of tasks; or computational efficiency.)\n\nIn other words, I was looking for a summary that would clearly answer: what is this for; what is this intended to replace; and what are its prospects at doing so in scaled up practical applications? \n\nTo better guide a revision, I will elaborate on several questions I had while reading this that might help with a tighter framing:\n- Empirical comparisons to existing ‘competitor operators’: were the FC-final layers the best comparison for the kinds of operations HRR might seek to replace? What about other hashing and distillation approaches? The authors mention that they replaced the hierarchical-attention based head in AttentionXML with an FC layer. This seems like a pretty major change, especially since learnable attention seems like one of the closer comparisons to the kind of querying that HRR can perform. Putting attention (or another common ‘competitor’ operation) through its paces with respect to HRR -- on a variety of metrics (computational efficiency, accuracy) would be useful.\n- Candidate as a useful symbolic operation in scaled up tasks and architectures: the XML task seems to be a good fit for HRR. But it would be even better if the authors could paint a picture of how or whether it could be used for other kinds of symbolic operations associated with Turing machines or modern programming languages -- for example, can HRR be used to preserve ordering and syntax, like a structured grammar? These are key reasons why symbolic components are often added to neural architectures, beyond query capacity. \n- Candidate as a practical operation in scaled up learnable tasks and architectures: the discussion of updating label vectors leaves open questions of how HRR would be practically incorporated into more complex learnable architectures -- when I think about attention-based architectures, for instance, one key aspect of their success is that they can play well with operations over implicit, learned vector representations. Beyond XML, could the authors give a picture (or suggest how future work might tackle) HRR operations in other modern tasks? Even better if these are tasks that intuitively require some learning and cannot be solved by a solely symbolic approach. \n\n====\n*Clarity review*: the paper is relatively clear in presenting the HRR operation and modifications made by the authors, though it is also notation dense (I’m not an expert, but I had to look up the basic circular convolution and seek external references to suggest why this operation should have benefits over other attention-style operations.) We might have benefitted (even in the supplement) from a worked example on a toy lookup task, as well as some figures showing how the operation works graphically (like those on the Wikipedia page about circular convolution!)\n\t\t- The discussion of the loss, however, is clear and useful relative to the more \ncommon cross-entropy loss.\n\n*Correctness review*: the approach overall appears correct. \n*Relation to prior work*: the authors extensively discuss prior work on HRRs. As discussed above, it would be useful if they could also take a step back and at least review the closest prior work outside of HRRs that we should consider this work to be comparable to in order to frame the best comparisons early on. \n\nTiny nits:\n\tL294-295: XXX lines of code.\n\tHRR is sometimes misspelled as ‘HHR’ throughout. :) \n", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "The authors make a good effort in the empirical section to discuss limitations of their existing framework on a real-world task, and against relatively reasonable baselines (though see above for a discussion of the FC choice.) They choose a variety of reasonable metrics and provide additional supplementary material discussing the additional ablations and experiments conducted.\n\tThey complete an author checklist, and (I believe) accurately assess the potential societal impacts.\n\n", "review_text": "", "extra_scores": {"ethical_concerns": "There are not ethical issues with this paper that I see as a reviewer.", "needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "2"}, "extra_text": {}}, {"review_id": "ErowHln7VB1", "reviewer": "Reviewer_uoCQ", "summary": "The authors study a small but important modification of holographic reduced representations (HRRs) which make them practical for use in differentiable neurosymbolic systems. They do a good job exploring the implications of this modification, though on a task (multi-label classification) which does not seem like a particularly exciting domain for HRRs, in the sense that it doesn't utilize what is arguably their key feature, namely the ability to represent complex symbolic knowledge.", "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": "This paper introduces a projection operator that initializes vectors to have a complex magnitude of 1. This has important practical implications for using these vectors in a holographic reduced representation, because it enables use of the inverse operator for decoding in a numerically stable way (rather than the approximate inverse, which was traditionally use because of its greater numerical stability).\n\nMy subjective view of this paper is that it presents a useful method, and a pretty detailed comparison between architectures and parametrizations, but the application domain (multi-label classification) isn't a particularly interesting one. HRRs were invented to do represent and reason about complex symbolic expressions. It would have been more interesting to see an application to the kinds of domains where neurosymbolic approaches have been applied recently (e.g., scene understanding, knowledge graphs, natural language inference).\n\nMy other major comment is that it's not clear what problem is being solved here that wasn't already solved. The authors concede that their approach is not intended to exceed performance of other algorithms on XML tasks, but rather to understand the pros and cons of using HRRs for this task. I feel like this is a rather weak case for using HRRs (though I agree with the authors that the advantage of the HRR in their comparisons is compelling). This connects back to my previous point, which is that a better case for HRRs might be made with a different task, one where symbolic reasoning is necessary.\n\nMinor:\n\nabstract: \"differential component\" -> \"differentiable component\" (?)\n\nabstract: \"differential solution\" -> \"differentiable solution\" (?)\n\nabstract: \"a output\" -> \"an output\"\n\nI don't understand the query example in the second paragraph of the introduction. Should this be the inverse operation applied to S and red? Why is there a convolution symbol in there?\n\np. 2: \"it’s niche\" -> \"its niche\"\n\np. 2: \"takle\" -> \"tackle\"\n\np. 3: \"it's values\" -> \"its values\"\n\np. 4: It looks odd to have an equation number (4) in the middle of an equation.\n\np. 7: \"XXX lines of code\" should be replaced with an integer.\n\np. 7: \"overal\" -> \"overall\"\n\np. 7: \"project step\" -> \"projection step\"\n\np. 7: \"largeness\" -> \"size\"\n\nI was confused by Table 1. Why are different sets of models being applied to different data sets? I didn't see any explanation of these choices.", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "I don't see any negative societal impact of the work. They have adequately addressed limitations.", "review_text": "", "extra_scores": {"needs_ethics_review": "No", "ethics_review_area": "", "time_spent_reviewing": "3.5"}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper shows how HRRs can be modified to enable end-to-end differentiable training at scale. While the results are not compelling that such representations will be useful in applications, the reviewers all agreed that the technical method is novel and provides a foundation for other systems to build on. 
Decision: Accept (Spotlight)