Technische Samenvatting: Generalized Holographic Reduced Representations (GHRR)

1. Probleemstelling

Hyperdimensional Computing (HDC), ook wel Vector Symbolic Architectures (VSA) genoemd, fungeert als een neurosymbolisch paradigma dat connectionistische en symbolische AI met elkaar verbindt. Het maakt gebruik van hoogdimensionale hypervectoren om data te representeren met eigenschappen zoals robuustheid, tolerantie voor ruis en samenstelling met een vaste breedte. Echter, standaard HDC-implementaties, met name Fourier Holographic Reduced Representations (FHRR), ondervinden aanzienlijke beperkingen bij het coderen van complexe compositional structuren:

• Commutativiteit van Binding: De standaard bindingoperatie in FHRR (elementsgewijze vermenigvuldiging van scalaire fasoren) is commutatief. Dit beperkt de mogelijkheid om asymmetrische structuren (bijv. sequenties, bomen) te coderen zonder te vertrouwen op externe technieken zoals permutaties of positionele coderingen, wat de representatie ingewikkeld maakt.
• Beperkte Expressiviteit: De bindingoperatie in FHRR fungeert als een holografische projectie met een lage capaciteit (effectief het nemen van de diagonaal van een tensorproduct). Dit beperkt het vermogen om voldoende informatie te behouden voor complexe interacties, zoals die vereist zijn voor attention-mechanismen in deep learning.
• Schaalbaarheid versus Efficiëntie: Hoewel deep learning generalisatie bereikt via enorme hoeveelheden data en rekenkracht, biedt HDC een efficiënter alternatief, maar mist momenteel de expressieve kracht om complexe structurele redenering aan te pakken zonder af te zien van zijn gewenste eigenschappen (transparantie, robuustheid, vaste breedte).

2. Methodologie: Generalized Holographic Reduced Representations (GHRR)

De auteurs stellen Generalized Holographic Reduced Representations (GHRR) voor, een uitbreiding van FHRR die de onderliggende algebraïsche structuur generaliseert om de bovenstaande beperkingen aan te pakken.

Kernwiskundig Kader

• Generalisatie van Elementen: Waar FHRR-hypervectoren bestaan uit elementen in de unitaire groep $U(1)$ (complexe scalairen met een eenheidsmagnitude), generaliseren GHRR deze elementen tot unitaire matrices in de groep $U(m)$ voor $m \geq 1$.
• Hypervectorstructuur: Een GHRR-hypervector $H$ is een tensor met dimensie $D \times m \times m$, weergegeven als $H = [A^{(1)}, \dots, A^{(D)}]^\top$, waarbij elke $A^{(j)} \in U(m)$.
• Operaties:
  • Bundeling (+): Elementsgewijze matrixoptelling.
  • Binding ($*$): Elementsgewijze matrixvermenigvuldiging. Dit is inherent niet-commutatief voor $m > 1$, waardoor de natuurlijke codering van orde en asymmetrische relaties mogelijk wordt.
  • Similariteit: Gedefinieerd als $\delta(H_1, H_2) = \frac{1}{mD} \text{Re} \left( \text{tr} \left( \sum_{j=1}^D A^{(j)} (B^{(j)})^\dagger \right) \right)$.

Theoretische Eigenschappen

Het artikel stelt vast dat GHRR voldoet aan de fundamentele eisen van HDC:

1. Kwasi-orthogonaliteit: Willekeurig bemonsterde basis-hypervectoren zijn kwasi-orthogonaal (similariteit $\to 0$ naarmate dimensie $D \to \infty$).
2. Binding-invariantie: Het resultaat van een bindingoperatie is kwasi-orthogonaal ten opzichte van zijn operanden, waardoor compositional structuren onderscheiden blijven van hun onderdelen.
3. Similariteitsbehoud: De similariteit tussen twee concepten blijft behouden bij binding met een derde concept.
4. Kernverbinding: GHRR behoudt de verbinding met Random Fourier Features (RFF). De similariteit tussen GHRR-coderingen benadert een verschuivingsinvariante kern. De matrixcomponent $Q$ in de decompositie $A = Q\Lambda$ maakt adaptieve kernen mogelijk, waarbij de kernvorm kan worden gemoduleerd door de invoer of de matrixstructuur.

Binding als Attention

Een belangrijke theoretische inzicht is dat GHRR-binding attention-mechanismen kan implementeren.

• In standaard Transformers wordt attention berekend als $\text{softmax}(QK^\top)V$.
• In GHRR spiegelt de bindingoperatie (matrixvermenigvuldiging) gecombineerd met de similariteitsfunctie (spoor van het product) wiskundig het attention-mechanisme.
• Door de matrixcomponenten $Q$ te behandelen als leerbare of vaste bases en $\Lambda$ als de data-codering, voert GHRR-binding effectief een gewogen som van waarden uit op basis van query-key-similariteit, maar binnen de hyperdimensionale algebra.

3. Belangrijkste Bijdragen

1. Introductie van het Kader: Het voorstellen van GHRR als een flexibele, niet-commutatieve uitbreiding van FHRR, met een specifieke implementatie met behulp van unitaire matrices $U(m)$.
2. Theoretische Bewijzen: Formeel bewijs dat GHRR voldoet aan HDC-eigenschappen (kwasi-orthogonaliteit, similariteitsbehoud) en zijn equivalentie met FHRR wanneer $m=1$.
3. Kern- en Bindinganalyse: Interpretatie van GHRR-binding als een interpolatie tussen FHRR-binding (diagonaalprojectie) en Tensor Product Representations (volledig tensorproduct). Het artikel toont aan dat binding in GHRR attention-mechanismen kan implementeren.
4. Empirische Validatie:
   • Niet-Commutativiteit: Aangetoond dat GHRR geneste dictionaries en bomen kan coderen zonder permutatie-operaties, in tegenstelling tot commutatief FHRR.
   • Decodernauwkeurigheid: Aangetoond dat het vergroten van $m$ (matrixgrootte) de decodernauwkeurigheid voor diepe compositional structuren (bomen) verbetert in vergelijking met FHRR.
   • Capaciteit: Geverifieerd dat GHRR de geheugencapaciteit van FHRR behoudt terwijl het niet-commutatieve mogelijkheden biedt.
   • Taalmodelleren: De standaard attention-mechanisme in een Transformer vervangen door een GHRR-variant. Het model is getest op Wikitext-2 en Penn Treebank datasets.

4. Experimentele Resultaten

• Niet-Commutativiteit: Bij taken voor dictionary-oproep faalde commutatief FHRR om waarden te onderscheiden met gepermuteerde sleutels, terwijl GHRR ($m=3$) succesvol de juiste waarden ophaalde.
• Decoderdiepte: Voor boomgestructureerde data behield GHRR met grotere $m$ een hoge decodernauwkeurigheid op grotere dieptes in vergelijking met FHRR. Interessant genoeg behield permutatie-gebaseerd FHRR aanvankelijk 100% nauwkeurigheid voor langere tijd, maar leed aan scherpe dalingen, terwijl GHRR genaderd op een meer genaturaliseerde manier.
• Capaciteit: GHRR toonde een vergelijkbare bundelcapaciteit als FHRR. Cruciaal, bij het onderscheiden tussen permutaties van gebonden hypervectoren, presteerde GHRR ($m > 1$) aanzienlijk beter dan FHRR ($m=1$), dat geen permutaties kon onderscheiden.
• Taalmodelleren: Het vervangen van Transformer attention door GHRR-binding resulteerde in een verbeterde perplexiteit (PPL) bij taalmodelleringsopdrachten:
  • Wikitext-2: Gemiddelde verbetering van 5,47%.
  • Penn Treebank: Gemiddelde verbetering van 2,75%.
  • De beste configuraties gebruikten verschillende positionele coderingen voor Query-, Key- en Value-matrices.

5. Betekenis en Claims

Het artikel claimt dat GHRR een flexibele, niet-commutatieve bindingoperatie biedt die de kloof overbrugt tussen de eenvoud van HDC en de expressieve kracht die vereist is voor complexe symbolische redenering en deep learning.

• Expressiviteit: GHRR-binding is expressiever dan andere HDC-varianten, in staat om attention-mechanismen direct te implementeren via matrixvermenigvuldiging, een eigenschap die niet aanwezig is in standaard VSA-binding.
• Efficiëntie en Robuustheid: Door de vaste breedte, holografische en robuuste aard van HDC te behouden, biedt GHRR een weg naar efficiënte, interpreteerbare AI-systemen die niet afhankelijk zijn van de enorme rekenbronnen van standaard deep learning.
• Neurosymbolische Integratie: Het kader ondersteunt transparante neuro-symbolische integratie, waardoor expliciete specificatie van structuur mogelijk is terwijl de leercapaciteiten van connectionistische modellen behouden blijven.
• Praktische Nut: Het succesvolle vervangen van Transformer attention door GHRR-binding toont aan dat hyperdimensional computing state-of-the-art deep learning-architecturen direct kan versterken, prestaties verbetert bij taalmodelleringsopdrachten en potentieel de reken- en data-eisen voor gestructureerde representatieleren verlaagt.

De auteurs concluderen dat GHRR nieuwe paden opent voor efficiënte, interpreteerbare AI door nauwkeurige codering en decoding van complexe compositional structuren mogelijk te maken zonder af te zien van de gewenste eigenschappen van traditionele HDC.