A Walsh Hadamard Derived Linear Vector Symbolic Architecture

We will add the explanations below to the manuscript to provide motivating reasons for each approach.

4.2.1:

When running on low-power computing environments, it is often desirable to offload the computation to a third-party cloud environment to get the answer faster and use fewer local resources. However, this may be problematic if one does not fully trust the available cloud environments. Homomorphic encryption (HE) is the ideal means to alleviate this problem, providing cryptography for computations. HE is currently more expensive to perform than running a neural network itself, defeating its own utility in this scenario. CSPS provides a heuristic means of obscuring the nature of the input (content), and output (number of classes/prediction), while also reducing the total local compute required.

4.2.2:

Extreme Multi-label (XML) is the scenario where, given a single input of size $d$, $C >> d$ classes are used to predict. This is common in e-commerce applications where new products need to be tagged, and an input on the order of $d \approx 5000$ is relatively small compared to $C \geq$ 100,000 or more classes. This imposes unique computational constraints due to the output space being larger than the input space and is generally only solvable because the output space is sparse --- often less than 100 relevant classes will be positive for any one input. VSAs have been applied to XML by exploiting the low positive class occurrence rate to represent the problem symbolically.

W1: The noted work is indeed valuable, though we can not implement it's experiments in the short rebuttal time. We will add the following paragraph to the manuscript.

As noted in (Steinberg and Sompolinsky), most VSAs can be viewed as a linear operation where $\mathcal{B}(a,b) = a^\top G b$ and $\mathcal{B}^*(a,b) = a^\top F b$, where $G$ and $F$ are $d \times d$ matrices. Hypothetically, these matrices could be learned via gradient descent, but would not necessarily maintain the neuro-symbolic properties of VSAs without additional constraints. Still, the framework is useful as VTB, HRR, MAP, HLB, and the original TPR all fit within this generalized representation. By choosing $G$ and $F$ with specified structure, we can change the computational complexity from $\mathcal{O}(d^2)$ (like TPR) to log-linear (like HRR), or $\mathcal{O}(d)$ for HLB and MAP.

W2 We will add a discussion of all these relevant related works to the paper and the wide and growing interest and applicability of VSAs in deep learning.

We have experiments for MAP-B in progress answering a question of reviewer xpT1. Our available computing resources are limited as we are trying to work through the MIMOConv code and make sure that we have altered it correctly and scheduled an experiment.

W3: Thank you for the typo identifications, they have been corrected!

W4: We were not able to determine why the non-projected Hadamard binding seems to work well for seemingly random and arbitrary dimension sizes of $d$ (not for a lack of trying, we spent about a month trying to understand what was happening without success). In all cases, our projected Hadamard ($\eta^\pi$ noise term) has lower error and behaves consistently across $\rho$ and $d$, and resolved the asperity we saw with the projection-less Hadamard. For this reason, our final HLB is superior to the intermediate method, so we did not consider it further. We will add this context to that appendix section.

Q1: see W1

Q2: see W2

Q3: see W4

Q4: Yes, we re-used the hyper-parameters from the prior papers. These were primarily the network architecture size and number of layers. All were trained with Adam and used the standard recommended learning rate.

Q5: The rescaling is useful as it allows the designing of a larger system to easily reason about their architecture. For example, if the unscaled dot product went into a softmax or other non-linearity, the expected behavior would change when the number of neurons/dimension $d$ changed. Having the scaling factor means that one can always (subject to noise) expect near-zero/one values for missing/present inputs. This is also critical to avoid vanishing gradients in the backward pass of a differentiable system.

W1: We will add the below explanation motivating the choice of the WHT to the manuscript:

Our motivation for using the WHT comes from its parallels to the FFT used to derive the HRR and the HRR's relatively high performance. The Hadamard matrix has a simple recursive structure, making analysis tractable, and its transpose is its own inverse, which simplifies the design of the inverse function $\mathcal{B}^*$. Like the FFT, WHT can be computed in log-linear time, though in our case, the derivation results in linear complexity as an added benefit. The WHT is already associative and distributive, making less work to obtain the desired properties. Finally, the WHT involves only $\{-1,1\}$ values, avoiding numerical instability that can occur with the HRR/FFT. This work shows that these motivations are well founded, as they result in a binding with comparable or improved performance in our testing.

W2: We have corrected all noted typos and done another editing pass to make sure none remain.

For the flow of Section 3, we will add the following content into the intro/starting paragraphs to help ease the reader through the section.

First, we will briefly review the definition of the Hadamard matrix $H$ and its important properties (see W1 above) that make it a strong candidate from which to derive a VSA. With these properties established, we will begin by deriving a VSA where binding and unbinding are the same operation in the same manner as which the original HRR can be derived[30]. Any VSA must introduce noise when vectors are bound together, and we will derive the form of the noise term as $\eta^\circ$. Unsatisfied with the magnitude of this term, we then define a projection step for the Hadamard matrix in a similar spirit to [8]'s complex-unit magnitude projection to support the HRR and derive an improved operation with a new and smaller noise term $\eta^\pi$. This will give us the HLB bind/unbind steps as noted in Table 1.

W3: We believe HLB performs better in deep learning tasks because it avoids exploding/vanishing gradients. This can be observed in Figure 3 where HLB has a consistent magnitude norm under multiple operations, and the avoidance of numerical instability with the FFT or other operations. We will add this note to the paper.

Q1: We believe so; see W3 note. In particular, the low performance of MAP-C despite similar mechanical operation points to a primary difference being the scale-sensitivity based on the number of bound/bundled terms.

Q2: There are pros/cons to symmetry in binding, as noted in [11]. Non-symmetric VSAs have an apparent advantage in representing hierarchical structures (e.g., a stack) with lower noise. However, they may not be as easy to use in certain symbolic contexts due to the lack of symmetry and the inability to unbind multiple values in a single operation. This will be added to the manuscript, though we note that we make no claim on a preference for one vs the other. We pursued a symmetric VSA in our work simply because we thought we could build one effectively.

Q3: $\mathcal{B}=\mathcal{B}^*$ was stating that in the context we used the same function for both binding and unbinding. This will be clarified in the revision.

This is the detailed step by step breakdown of the Theorem 3.1

$\mathcal{B}^{*}(\mathcal{B}(x\_1, y\_1) + \cdots + \mathcal{B}(x\_\rho, y\_\rho), y\_i^\dagger)$

$= \mathcal{B}^{*}(\frac{1}{d} \cdot H (H x\_1 \odot H y\_1) + \cdots + \frac{1}{d} \cdot H (H x\_\rho \odot H y\_\rho), y\_i^\dagger)$

$= \frac{1}{d} \cdot H ((H x\_1 \odot H y\_1 + \cdots + H x\_\rho \odot H y\_\rho) \odot \frac{1}{H y\_i})$

$= \frac{1}{d} \cdot H (H x\_1 \odot H y\_1 \odot \frac{1}{H y\_i} + \cdots + H x\_i \odot H y\_i \odot \frac{1}{H y\_i} + \cdots + H x\_\rho \odot H y\_\rho \odot \frac{1}{H y\_i})$

$= \frac{1}{d} \cdot H (H x\_1 \odot H y\_1 \odot \frac{1}{H y\_i} + \cdots + H x\_i + \cdots + H x\_\rho \odot H y\_\rho \odot \frac{1}{H y\_i})$

$= \frac{1}{d} \cdot H (H x\_i + \frac{1}{H y\_i} \odot \sum\_{\substack{j=1,j \neq i}}^{\rho} (H x\_j \odot H y\_j))$

$= x\_i + \frac{1}{d} \cdot H (\frac{1}{H y\_i} \odot \sum\_{\substack{j=1, j \neq i}}^{\rho} (H x\_j \odot H y\_j) )$ Applying Lemma 3.1

Then we get $= x\_i$ if $\rho = 1$, but otherwise we have the noise term for $\rho > 1$ where $x\_i + \eta\_i^\circ$. Where $\eta\_i^\circ = \frac{1}{d} \cdot H (\frac{1}{H y\_i} \odot \sum\_{\substack{j=1, j \neq i}}^{\rho} (H x\_j \odot H y\_j) )$

Q4: Equation (5) has the same operations as theorem 3.1, except Equation (5) includes a projection step when theorem 3.1 does not. It shows that we end up with a different description of the error term $\eta$ when adding a projection step that is easier to analyze and work with. This will be added to the revision.

W1: Thank you for the typo catches, they have been fixed!

W2: For CSPS each network has four (convolutional) U-Net rounds in every experiment and doubles from 64 filters after each round, halving in size for the decode. The local prediction network has 4 convolutional layers, with max-pooling after each round, followed by three linear layers of 2048, then 1024, and finally, the $K$ classes of neurons.

For XML, two hidden layers on a fully connected input for each dataset are used. The dimension $d=400$ for the smaller datasets and $d=3000$ for Amazon-13K and larger datasets. This is significantly less memory than a $d \times L$ matrix for normal BCE where $L$ is up to 200k in our experiments.

Each of 4.2.1 and 4.2.2 included this briefly in text, but was clearly not sufficient. For 4.2.1, we will add a new figure to help summarize (see one-page PDF). For 4.2.2., we will add a brief explanation, please see the one-page PDF again as the equations don't render properly in markdown/OpenReview.

Q1: The 2-norm of the composite representation $\chi$ can be approximated as $\sqrt{d \cdot \rho}$. Thus solving $\|\chi\|\_2 = \sqrt{d \cdot \rho}$ gives $\rho = \|\chi\|\_2^2 \cdot d^{-1}$. This is a good estimate of $\rho$ with a R-square value of $0.9865$, please see the rebuttal 1-page PDF for a plot of this relationship.

Q2: HLB and MAP have $\mathcal{O}(d)$ complexity, whereas HRR is $\mathcal{O}(d \log d)$ (for an FFT), and VTB has $\mathcal{O}(d \sqrt{d})$ (for $\sqrt{d}$ matrix-vector products of $\sqrt{d}^2$ cost each). We will add this to the manuscript.

Q3: MAP-C is used because it is the version of MAP that allows continuous vector values. Other variants of MAP require integer values, and thus can't be differentiated. So MAP-C is the logical point of comparison and is shortened to "MAP" in the manuscript. We will explain this in the revision; thank you.

Q4: For FHHR, we clarify that our experiments use the projected HRR of [8], which enforces complex unit magnitude -- and is thus equivalent to FHHR and uses an exact unbinding operation. Given that [8] and [1] both found the projection step necessary for good performance, we did not see value in running the original unprotected HRR.

For MAP-B (MAP with binary initialization), we were able to run the CSPS experiment, which still shows MAP-B performing worse than our HLB. The result is below, and we are still running the XML experiments during the rebuttal phase. Once completed they will go into the main paper. Still, it is clear that MAP-B does not outperform MAP-C, let along our HLB, indicating the initialization was not a singularly important difference.

MNIST: 98.40%

SVHN: 92.43%

CIFAR-10: 82.83%

CIFAR-100: 57.76%, 84.63%

MiniImageNet: 57.91%, 82.81%

GM: 75.90%, 83.72%

The XML results thus far: