Technische Samenvatting: Het Scheiden van Geometrische en Algorithmische Compressie via Voltooiing van Cayley-tabellen

1. Probleemstelling

Het artikel identificeert een fundamentele theoretische kloof in de Statistische Leertheorie (SLT) tussen Geometrische Compressie en Algorithmische Compressie.

• Geometrische Compressie: Moderne deep learning vertrouwt op continue mechanismen voor capaciteitscontrole (bijvoorbeeld regularisatie op basis van normen, maximalisatie van de marge, bias naar lage rang). Deze methoden gaan ervan uit dat parsimonische concepten liggen op gladde variëteiten of laag-dimensionale lineaire deelruimten. Hoewel deze benadering succesvol is voor continue data, faalt dit paradigma bij het extrapoleren van exacte algorithmische of discrete algebraïsche regels.
• Algorithmische Compressie: Klassieke leertheorie (PAC-leren, Ockhams scheermes, MDL) vormde leren in als het herstel van exacte, minimale logische regels. Het optimaliseren van discrete algorithmische complexiteit is echter over het algemeen NP-moeilijk, wat heeft geleid tot het feit dat moderne SLT dit grotendeels heeft opgegeven.
• De Kloof: Deep learning mist een inductieve bias gericht op minimalisatie van algorithmische complexiteit. Bijgevolg worstelen neurale netwerken met taken die exacte discrete algebraïsche structuren vereisen (bijvoorbeeld lengte-generalisatie op algorithmische taken, het ontdekken van exacte symmetrieën), en grijpen ze vaak terug op breekbaar memoriseren in plaats van regelabstractie.

Het artikel stelt voltooiing van Cayley-tabellen voor als de canonieke testomgeving om deze ontbrekende bias aan te pakken. Deze taak omvat het herstel van een discrete binaire operatie (een groeps- of quasigroepsstructuur) uit partiële waarnemingen, en fungeert als het discrete algebraïsche tegenhanger van matrixvoltooiing.

2. Methodologie en Theoretisch Kader

De Canonieke Taak: Voltooiing van Cayley-tabellen

In tegenstelling tot Matrixvoltooiing, dat streeft naar lage lineaire rang (waarbij rijen lineair afhankelijk zijn), zijn Cayley-tabellen van groepen Latijnse vierkanten waarbij rijen permutaties van elkaar zijn. Deze structuur sluit lineaire redundantie inherent uit. De ware parsimonie van algebraïsche groepen vloeit voort uit het associativiteitsaxioma, dat de globale structuur beperkt om de lengte van de structurele beschrijving te minimaliseren.

Operator-gebaseerde Tensorfactorisatie

Om dit op te lossen zonder onbeheersbare combinatorische zoektocht, maakt het artikel gebruik van een continue, differentieerbare aanpak gebaseerd op recent werk van Huh (2025):

1. Tensorrepresentatie: De binaire operatie $\circ$ op een eindige verzameling $Q$ van grootte $n$ wordt weergegeven door een structuurtensor $\delta \in \{0, 1\}^{n \times n \times n}$, waarbij $\delta_{abc} = 1$ als $a \circ b = c$.
2. Factorisatiemodel: De tensor wordt gemodelleerd via een operator-gebaseerde factorisatie:
   $$T_{abc}(\Theta) := \frac{1}{n} \text{Tr}(A_a B_b C_c)$$
   waarbij $\Theta = (A, B, C)$ en $A_a, B_b, C_c$ matrix-schijven van $n \times n$ zijn (lineaire operatoren).
3. Vlakke Prior: De optimalisatiedoelfunctie bevat een vlakke prior die de trace van de Hessiaan van het empirische reconstructieverlies straft:
   $$H(\Theta) := \text{Tr}\left(\nabla^2 \sum_{(a,b,c) \in \Omega} (T_{abc}(\Theta) - \delta_{abc})^2\right)$$

Variatiekarakterisering

De doelfunctie $H(\Theta)$ decomposeert in twee kritieke componenten die discrete eigenschappen induceren:

• Geometrische Uitlijning (Collineariteit): Handhaaft het associativiteitsaxioma.
• Inverse $\ell_2$-Straf: Werkt als een exacte inverse-rangstraf binnen het collineaire variëteit.

Cruciaal is dat dit mechanisme parameters drijft naar volledige rang-unitariteit, wat diametraal tegenovergesteld is aan de lage-rang-bias van standaard geometrische compressie.

3. Belangrijkste Resultaten en Bewijzen

Het artikel presenteert de volgende theoretische bevindingen gebaseerd op het voorgestelde kader:

• Exact Herstelgrens: In de limiet van volledig waargenomen data wordt bewezen dat de geometrische infimum $H_{\inf}(\delta) := \inf_{T(\Theta)=\delta} H(\Theta)$ een exacte, differentieerbare maatstaf is voor algebraïsche complexiteit.
• Ondergrens: De doelfunctie stelt een absolute ondergrens vast $H_{\inf}(\delta) \ge 3|\delta|$ (waarbij $|\delta| = n^2$).
• Karakterisering van Minimalisatoren: Deze grens wordt bereikt dan en slechts dan als de doeloperatie isotopisch is met een groep. In dit geval karakteriseert de globale minimalisator uniek de reguliere representatie van de onderliggende groep (op unitaire gauge na).
• Proof of Concept: Dit levert een formeel bewijs dat continue, op gradiënten gebaseerde optimalisatie in staat is om discrete algebraïsche axioma's (specifiek associativiteit) op native wijze te ontdekken zonder terug te grijpen op combinatorische zoektochten.

4. Gestelde Open Problemen

Het artikel daagt de gemeenschap uit om de scheiding tussen geometrische en algorithmische compressie te formaliseren via twee specifieke open problemen:

1. Open Probleem 1 (Formele Scheiding): Stel een strikt scheidingsstelling op tussen geometrische capaciteitscontrole (bijvoorbeeld Rademacher-complexiteit, margengrenzen) en algorithmische compressie. Het doel is om hypotheseklassen (bijvoorbeeld discrete algebraïsche regels) te karakteriseren waarbij puur geometrische generalisatiegrenzen bewezen leeg zijn (waarbij exponentiële steekproefcomplexiteit vereist is), terwijl differentieerbare algorithmische complexiteitsmaten strakke, polynoomgaranties opleveren.
2. Open Probleem 2 (Steekproefcomplexiteit van Cayley-tabelvoltooiing): Formaliseer een exacte herstelgarantie voor de door vlakheid geregulariseerde tensorfactorisatie. Kan er namelijk worden bewezen dat de globale minimalisator de groeptabel met hoge waarschijnlijkheid perfect voltooit, gegeven slechts $O(n \log n)$ uniform gesampleerde ingangen? Dit zou contrasteren met de standaard theorie van matrixvoltooiing, die leegte grenzen oplevert die $O(n^2)$ overschrijden voor structuren met volledige rang.

5. Betekenis en Beperkingen

Betekenis

Het artikel betoogt dat het formaliseren en oplossen van het probleem van Cayley-tabelvoltooiing zou:

• Een rigoureuze wiskundige brug vormen tussen het klassieke, door logica gedreven tijdperk en het moderne, door geometrie gedreven tijdperk van SLT.
• Een proof-of-concept bieden dat zorgvuldig ontworpen, puur continue prioren gradient descent kunnen dwingen om exacte combinatorische eigenschappen op native wijze te optimaliseren.
• De kritieke ontbrekende fundamenten in SLT aanpakken op de terreinen waar geometrische surrogaten falen en algorithmische compressie slaagt.

Beperkingen en Huidige Stand

• Partiële Resultaten: Het artikel erkent dat hoewel existentiebewijzen en landschapsanalyses bestaan (Huh, 2025), de fundamentele vraag naar de exacte theoretische grens open blijft.
• Neurosymbolische Beperkingen: Huidige neurosymbolische benaderingen worden bekritiseerd omdat ze logica óf verzwakken tot benaderende waarschijnlijkheden (wat het herstel van rigide structuren verhindert) óf vertrouwen op externe symbolische engines om logische beperkingen te hanteren (wat native algorithmische ontdekking verhindert).
• Scope: Het artikel richt zich op het vaststellen van het theoretische kader en het stellen van de open problemen. Het claimt niet binnen deze tekst de steekproefcomplexiteitsgrenzen (Open Probleem 2) of het algemene scheidingsstelling (Open Probleem 1) opgelost te hebben, maar positioneert deze eerder als de noodzakelijke volgende stappen voor het vakgebied.