Torus embeddings

Dit paper introduceert torus-embeddings als een computerefficiënt alternatief voor Euclidische en hypersferische representaties, waarbij wordt aangetoond dat deze aanpak vergelijkbare prestaties biedt en een directe route opent naar efficiënte TinyML-implementaties via quantisatie.

De kern

De Kern: Een Nieuwe Manier om Data te Bewaren

Stel je voor dat je een enorme bibliotheek hebt met miljoenen boeken (data). Om deze boeken snel te vinden, moet je ze op een slimme manier rangschikken. In de wereld van kunstmatige intelligentie (AI) noemen we deze rangschikking een "embedding".

Meestal doen computers dit op twee manieren:

1. Op een vlakke kaart (Euclidisch): Zoals een platte wereldkaart.
2. Op een bol (Hypersfeer): Zoals de aarde, waar alles op het oppervlak ligt.

De auteur, Dan Stowell, stelt een derde optie voor: De Torus.

Wat is een Torus? (De Donut-analogie)

In de wiskunde is een torus een vorm die op een donut of een zwemband lijkt.

• De Bol: Als je op de aarde (een bol) naar het noorden loopt, kom je uiteindelijk weer uit bij het zuiden. Je kunt niet "voorbij" de rand lopen.
• De Torus: Stel je een zwemband voor. Als je erop loopt en je gaat naar het "rechter" einde, kom je direct weer uit aan de "linkerkant". Als je naar "boven" gaat, kom je weer uit bij "onder". Er zijn geen randen, maar het is een gesloten lus in elke richting.

Waarom is dit slim voor computers?

Hier komt het slimme stukje van het artikel.

Het probleem met de Bol:
Computers zijn eigenlijk heel goed in het tellen met hele getallen (zoals 0 tot 255). Maar als je een bol wilt tekenen met deze getallen, krijg je een probleem. De coördinaten op een bol zijn vaak "raar" en niet-lineair. Het is alsof je probeert een bol te maken met Legoblokjes die alleen maar recht kunnen staan; het wordt een klungelige, onnauwkeurige bol. Om dit op te lossen, moeten computers vaak ingewikkelde rekenstappen doen, wat tijd en energie kost.

De oplossing met de Torus:
De Torus past perfect bij hoe computers werken.

• Denk aan een ouderwetse odometer in een auto (de teller voor kilometers). Als je bij 9999 km bent en je rijdt nog een stukje, springt hij terug naar 0000. Dat is "overloop" (overflow).
• Voor een computer is dit heel normaal en heel snel.
• Een Torus is precies zo'n "overloop"-wereld. Als je aan de rechterkant van de wereld bent en je gaat nog een stapje verder, ben je automatisch weer aan de linkerkant.

De Analogie:

• De Bol is als proberen een wereldbol te maken van papier: je moet het papier knippen en plakken, en het wordt kreukelig.
• De Torus is als een Pac-Man-spel. Als Pac-Man aan de rechterkant van het scherm verdwijnt, komt hij direct aan de linkerkant weer tevoorschijn. De computer hoeft niet na te denken over "randen" of "overloop", het is zijn natuurlijke taal.

Wat heeft de auteur ontdekt?

Stowell heeft getest of je AI-modellen kunt trainen die direct in deze "Pac-Man-wereld" (de Torus) werken, in plaats van de traditionele "Bol-wereld".

1. Het werkt net zo goed: De AI leert net zo snel en maakt net zo weinig fouten als met de traditionele bol-methode.
2. Het is sneller en zuiniger: Omdat de Torus perfect past bij de simpele "hele getallen" (integers) die elke gewone processor (zoals in je telefoon of oude laptop) gebruikt, hoeft de computer geen zware wiskunde te doen.
3. Kleine getallen, grote kracht: Zelfs als je de data heel klein maakt (bijvoorbeeld door ze te comprimeren tot heel weinig bits), blijft de Torus-wereld goed werken. De Bol-wereld wordt dan vaak rommelig en onnauwkeurig.

Waarom is dit belangrijk voor de toekomst?

We leven in een tijd van "TinyML" (kleine AI op kleine apparaten). Denk aan slimme horloges, sensoren in de natuur, of oude computers.

• Deze apparaten hebben vaak geen krachtige videokaarten (zoals in datacenters), maar simpele processoren.
• De Torus-methode maakt het mogelijk om slimme AI-modellen te maken die op deze simpele apparaten kunnen draaien, zonder dat ze veel batterij verbruiken of veel geheugen nodig hebben.

Samenvattend in één zin:

De auteur heeft ontdekt dat we AI-data niet hoeven te persen in een ronde bol (wat voor computers lastig is), maar dat we ze beter in een "zwemband-vorm" (Torus) kunnen stoppen, omdat dit precies past bij hoe computers tellen, waardoor ze sneller, zuiniger en makkelijker op kleine apparaten werken.

Technische samenvatting

Titel: Torus Embeddings

Auteur: Dan Stowell (Tilburg University & Naturalis Biodiversity Centre)
Doel: Het onderzoeken van torus-gebaseerde representaties voor diep leren als een efficiënt alternatief voor de gebruikelijke hypersferische of Euclidische ruimtes, specifiek gericht op kwantisatie en implementatie op standaard hardware.

---

1. Het Probleem

In het huidige tijdperk van diep leren (DL) worden data-representaties (embeddings) vaak getraind in onbeperkte Euclidische ruimtes ($\mathbb{R}^D$) of beperkt tot een hypersfeer (via $L_2$-normalisatie). Hoewel hypersferische ruimtes goede eigenschappen hebben voor afstandsberekening en stabiliteit, zijn ze niet optimaal afgestemd op de fundamentele numerieke representatie in de meeste computersystemen.

• Hardware-mismatch: De meest efficiënte en wijdverspreide numerieke representatie in CPU's is het gebruik van gehele getallen (integers) met "overflow" (modulo) aritmetiek, vaak 8-bit (uint8).
• Topologische discrepantie: Vectoren van gehele getallen met modulo-aritmetiek vormen van nature de topologie van een torus (of hypertorus), niet een hypersfeer.
• Inefficiëntie: Het gebruik van hypersferische embeddings vereist vaak complexe kwantisatiemethoden of coderings-schema's om ze op integer-hardware te gebruiken, wat leidt tot verloren representatiecapaciteit en extra rekentijd.
• TinyML-behoefte: Er is een groeiende behoefte aan embeddings die direct en efficiënt kunnen worden uitgevoerd op lage-energie, standaard hardware (zoals oude en nieuwe CPU-architecturen) zonder de noodzaak van gespecialiseerde hardware (zoals GPU's/TPU's) of zware floating-point berekeningen.

2. Methodologie

De auteur "draait het probleem om": in plaats van de numerieke representatie aan te passen aan de topologie, kiest men een topologische ruimte die natuurlijk overeenkomt met de basis van computergetallen: de (hyper)torus.

Kernconcepten:

• Topologie: Een vector van gehele getallen met overflow-gedrag correspondeert met een vlakke, vierkante torus.
• Training in Torus-ruimtes: Omdat een torus een cyclische topologie heeft, kunnen standaard methoden zoals hyperplannen of softmax niet direct worden toegepast. De auteur gebruikt contrastief leren (SupCon) gebaseerd op afstanden.
• De Dilemma-oplossing (Clifford-projectie): De afstand in een vlakke torus is complex om te berekenen (veel mogelijke kortste paden). Om dit op te lossen, wordt gebruikgemaakt van een Clifford-torus. Dit is een inbedding van de vlakke torus in een hogere dimensie waarbij alle punten een vaste $L_2$-norm hebben. Hierdoor wordt cosinus-afstand een efficiënt en natuurlijk afstandsmaat, vergelijkbaar met hypersferische embeddings.

Twee strategieën voor het creëren van Torus-embeddings:

1. Clifford-projectie (torusC):
   • Transformeert elke dimensie $x_i$ naar $(\sin(x_i), \cos(x_i))$.
   • Verdubbelt de extrinsieke dimensie (van $D$ naar $2D$), maar behoudt de intrinsieke dimensie.
   • Nadeel: Kan instabiel zijn tijdens training; grote gradiëntupdates kunnen "omwikkelen" (wrap-around) en leiden tot divergentie.
2. Paarsgewijze $L_2$-normalisatie (torusN):
   • Past $L_2$-normalisatie toe op paren van dimensies: $(x_{2i-1}, x_{2i}) \rightarrow \frac{(x_{2i-1}, x_{2i})}{\|(x_{2i-1}, x_{2i})\|_2}$.
   • Behoudt de extrinsieke dimensie, maar halveert de intrinsieke dimensie (van $D$ naar $D/2$).
   • Voordeel: Zeer stabiel tijdens training, vergelijkbaar met standaard $L_2$-normalisatie op een hypersfeer.

Extra trainingstechnieken:

• KoLeo Regularisatie: Wordt gebruikt om de data-punten uniform over de ruimte te verspreiden (repulsieve kracht tussen buren), wat essentieel is voor een efficiënt gebruik van de bit-range.
• Gradiënt-Clipping: Essentieel, vooral voor torusC, om instabiliteit door grote updates te voorkomen.

Inferentie:
Tijdens inferentie kunnen de embeddings worden omgezet naar de "vlakke torus" (flat torus) representatie via arctan2. Hierdoor kunnen afstanden worden berekend met simpele integer-subtracties die overflow toestaan (wrap-around), wat extreem efficiënt is op CPU's.

3. Belangrijkste Bijdragen

1. Aanpassing van DL-frameworks: Het tonen dat standaard deep learning pipelines eenvoudig kunnen worden aangepast om embeddings met een inherente toroidale topologie te genereren.
2. Stabiliteitsanalyse: Het vaststellen dat de normalisatie-gebaseerde strategie (torusN) leidt tot training met stabiele en prestatie-eigenschappen die vergelijkbaar zijn met standaard hypersferische normalisatie, terwijl de Clifford-projectie (torusC) meer aandacht vereist.
3. Kwantisatie-onderzoek: Het aantonen dat torus-embeddings uitstekend geschikt zijn voor kwantisatie. Ze behouden hoge fideliteit zelfs bij extreem lage bitrates (bijv. 8-bit of 1-bit), wat cruciaal is voor "TinyML" toepassingen.
4. KoLeo Effectiviteit: Het tonen aan dat KoLeo regularisatie nuttig is voor het trainen van hypertoroidale representaties, hoewel de optimale instelling dimensie-afhankelijk is.

4. Resultaten

De auteurs hebben experimenten uitgevoerd op drie fronten: CIFAR-10/100 (beeld), en BIRB (vogelzang audio).

• Prestaties (Floating Point):
  • De torusN methode levert prestaties op die vergelijkbaar zijn met hypersferische embeddings (vaak iets lager, maar statistisch significant vergelijkbaar).
  • torusC was minder stabiel, vooral bij lagere dimensies.
  • Hypersferische embeddings presteerden over het algemeen iets beter, maar het verschil was klein.
• Kwantisatie (8-bit en Product Quantisation - PQ):
  • Bij 8-bit kwantisatie waren de prestaties voor zowel torus als hypersfeer zeer goed en vergelijkbaar.
  • Bij extreme compressie (1-bit of lage PQ-bitrates) presteerde torusN soms beter dan hypersferische embeddings, vooral bij lagere dimensies.
  • Product Quantisation (PQ) bleek zeer effectief voor beide topologieën, zelfs bij hoge compressie, wat suggereert dat hypersferische embeddings toch goed kwantiseerbaar zijn ondanks hun niet-rechte vorm.
• Few-Shot Learning (Audio):
  • Bij het classificeren van vogelzang (BIRB dataset) presteerden beide methoden goed.
  • torusN deed het beter bij lagere dimensies (16D en 32D) in few-shot scenario's, terwijl hypersferische embeddings beter deden bij hogere dimensies (128D).
• Efficiëntie:
  • Torus-embeddings bieden een directe route naar efficiënte implementatie op CPU's via integer-overflow, zonder complexe lookup-tabellen die nodig zijn bij andere kwantisatiemethoden.

5. Betekenis en Conclusie

Het paper introduceert een paradigmaverschuiving in het ontwerp van embeddings voor schaalbare en energiezuinige AI:

• Hardware-Afstemming: Torus embeddings zijn de natuurlijke keuze voor systemen die gebruikmaken van standaard integer-aritmetiek met overflow. Dit maakt ze ideaal voor TinyML en implementaties op wijdverspreide, lage-energie hardware.
• Kostenbesparing: Hoewel hypersferische embeddings momenteel de standaard zijn, biedt de torus een "vlakke" topologie die direct vertaalbaar is naar gehele getallen, wat de complexiteit van kwantisatie en inferentie drastisch verlaagt.
• Toekomstperspectief: Hoewel torus embeddings niet altijd superieur zijn in pure nauwkeurigheid ten opzichte van hypersferen, bieden ze een unieke combinatie van vergelijkbare prestaties en superieure efficiëntie bij implementatie. Dit is essentieel voor de toekomst van AI, waarbij de focus verschuift van het trainen van enorme modellen naar het efficiënt distilleren en inzetten van deze modellen op diverse apparaten.

Kortom, het paper bewijst dat het "omkeren" van het probleem (kiezen voor een topologie die past bij de hardware in plaats van andersom) leidt tot robuuste, efficiënte en goed presterende embeddings die direct inzetbaar zijn in de realiteit van beperkte rekenkracht.