Summary
This work describes a novel vector-symbolic architecture with linear-complexity binding/unbinding operations which includes the following components:
- A novel binding/unbinding scheme based on the Walsh-Hadamard transform, which reduces to element-wise multiplication and division due to the self-inverse properties of the Hadamard matrix, the definition of the binding operation, and the proposed projection step.
- Initialization of hypervector entries following a bimodal Gaussian distribution for purposes of numerical stability.
- A hypervector projection step which in expectation reduces the amount of noise which is incurred by unbinding a vector from a sum of bindings of pairs of vectors. It also simplifies the final form of the bind/unbind operations.
- A correction factor that is applied to augment the similarity score when retrieving from a sum of bound vectors, when the number of terms in the sum is known.
The authors experimentally test the effectiveness of their novel VSA scheme in several tasks including pure synthetic VSA tasks, as well as two tasks in which VSA schemes have previously been combined with deep neural networks.
Strengths
- The paper is written clearly.
- The experimental results in section 4.2 are convincing.
- The noise-reducing projection step is an interesting idea. Although the idea is not novel in itself, the definition of the specific projection step is novel as it is well applied in this novel context of Hadamard-derived binding.
- This VSA is highly efficient, including only element-wise operations.
- The final HLB bind/unbind operations are trivially simple, but there is a novelty and potentially useful insight in their derivation.
Weaknesses
1) Perhaps, it is worth mentioning and if possible elaborating/comparing with other parameterizable binding schemes such as "Steinberg and Sompolinsky, Associative memory of structured knowledge. Sci Rep 12, 21808 (2022)". This binding scheme is based on a trainable matrix. In fact, this parameterized binding scheme is generic by providing a continuum choice from d (VSA) to d^2 (TPR) for d-dimensional embeddings.
2) Besides the synthetic VSA tasks, out of the studied VSA+deep-learning applications, the XML classification results look very promising and practical (although CSPS looks interesting, it is a pseudo-encryption and hence heuristic). The reviewer was wondering if the proposed HLB binding and unbinding operators could have an edge in other hybrid VSA+deep-learning architectures such as:
- [27] where MIMOConv used HRR-based binding and MBAT-based unbinding, and MIMOFormer used MAP-based binding and unbinding
- Another neuro-symbolic capability of HRRs was studied in "M. Hersche, et al. A neuro-vector-symbolic architecture for solving Raven’s progressive matrices. Nat Mach Intell 5, 363–375 (2023)". Particularly, fractional power encoding was used to describe a set of arithmetic rules with binding and unbinding for abductive reasoning.
- Another closely related work to XML classification in which the number of classes C is larger than dimension (d << C) is "M. Hersche, et al. Factorizers for Distributed Sparse Block Codes. Neurosymbolic Artificial Intelligence, 2024". Would be interesting to see how HLB can handle sparse (block-wise) codes.
3) The other key issue with the paper is flaws in its presentation. Some of them are:
- The sentences starting at lines 39 and 40 are fully out of place.
- Line 107 mentions an “unburdening” operation, clearly referring to “unbinding”.
- Line 197 "HLBuses" needs spacing
- In Theorem 3.1, the \cdot multiplication notation was used in place of the \odot for element-wise multiplication used otherwise in the paper.
- Properties 3.1 is formulated in a weird way: “Let x sampled from omega holds the following properties…”
- In properties 3.1, it seems that an expectation operator is missing in the final property concerning the L2-norm of x sampled from MiND.
4) The blue horizontal strip at the top of Figure 4 is a weird anomaly which was not addressed by the authors.
Questions
- It would be great to elaborate on other trainable biding schemes discussed in (1) weaknesses
- If time and compute resources allow, it would be interesting to have more results based on the VSA neuro-symbolic architectures pointed out in (2) weaknesses, especially since the first two works have code repositories publically available.
- What is the reason behind the blue horizontal strip at the top of Figure 4?
- I did not fully understand what the hyperparameter search procedure for experiments in Section 4.2 was. Did the authors re-use the hyperparameters from the experiments in the referenced papers?
- In which scenarios is the discussion in section 3.2 relevant? The proposed factor only scales the similarity values, it does not modify the rankings of similarity scores, so it is not entirely clear to me in which context this matters.
Limitations
This work has no negative societal impact.