🤖 machine learning

Do Neural Networks Really Beat the Curse of Dimensionality? A Bit-Complexity View

Dit artikel betoogt dat wanneer benaderingsefficiëntie wordt geëvalueerd via computationele bitcomplexiteit in plaats van het aantal parameters, geen enkele methode de intrinsieke limieten die door metrische entropie worden gesteld fundamenteel overtreft, wat onthult dat de vermeende voordelen van neurale netwerken vaak voortkomen uit verschillen in de complexiteit van de functieklasse in plaats van architecturale superioriteit, en de traditionele "vloek van dimensionaliteit" herformuleert als een meer fundamentele "vloek van bitcomplexiteit".

Oorspronkelijke auteurs: Tong Mao, Jinchao Xu

Gepubliceerd 2026-08-04

📖 8 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tong Mao, Jinchao Xu

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je een complex, hoogdimensioneel object probeert te beschrijven—zoals een kolkende sterrenstelsel of een gelaagde taart—aan een vriend die alleen eenvoudige, platte tekeningen kan begrijpen. In de wereld van de informatica en wiskunde staat dit bekend als een "hoogdimensioneel benaderingsprobleem". Decennialang hebben wetenschappers gevochten tegen een beruchte vijand genaamd de "vloek van de dimensionaliteit". De naam klinkt eng, maar het idee is simpel: naarmate het aantal variabelen (of dimensies) in een probleem groeit, explodeert de hoeveelheid informatie die nodig is om het accuraat te beschrijven. Het is alsof je probeert een schilderij te maken van een 100-dimensionaal object; het aantal penseelstreken dat nodig lijkt te zijn, groeit zo snel dat het onmogelijk wordt om de klus te klaren.

Lama lang was de standaardmanier om te meten hoe goed een computer deze problemen oplost, het tellen van "parameters". Beschouw parameters als de knoppen, draaiknoppen en instellingen op een machine. Als een methode minder knoppen gebruikt om hetzelfde resultaat te behalen, wordt deze als efficiënter beschouwd. Onlangs zijn neurale netwerken (de AI-systemen die zaken als beeldherkenning en taalmodellen aandrijven) geprezen omdat ze deze vloek lijken te doorbreken. Ze lijken hoogdimensionele problemen op te lossen met een aantal knoppen dat niet explodeert naarmens de dimensies groeien, wat velen doet geloven dat ze de magische sleutel hebben gevonden om de meest complexe problemen in de wetenschap te ontgrendelen.

Er zit echter een addertje onder het gras dat vaak over het hoofd wordt gezien. In de echte wereld slaan computers getallen niet met oneindige precisie op; ze slaan ze op als reeksen enen en nullen, of "bits". Elke knop op die machine moet worden gecodeerd in een specifelijk aantal bits om te kunnen worden opgeslagen en berekend. Deze paper stelt een fundamentele vraag: als we stoppen met het tellen van de knoppen en beginnen met het tellen van de werkelijke bits aan informatie die nodig is om die knoppen op te slaan, zien neurale netwerken er dan nog steeds uit als magie? De auteurs, Tong Mao en Jinchao Xu, duiken diep in deze vraag door gebruik te maken van een concept genaamd "metrische entropie" (wat in essentie meet hoeveel informatie er minimaal nodig is om een vorm of functie te beschrijven) om te zien of neurale netwerken de vloek werkelijk verslaan of dat ze de kosten slechts op een andere manier verbergen.

De Grote Bit-Telling Roofoverval

De auteurs van deze paper, Tong Mao en Jinchao Xu, besloten hun detectivehoed op te zetten en naar de "vloek van de dimensionaliteit" te kijken vanuit een nieuwe hoek. In plaats van alleen te tellen hoeveel parameters (knoppen) een methode gebruikt, vroegen zij: "Hoeveel bits aan geheugen kost het eigenlijk om die knoppen op te slaan en een goed antwoord te krijgen?"

Om hun onderzoek te begrijpen, stel je voor dat je een gladde, rollende heuvel probeert te beschrijven voor een robot.

De Oude Manier (Parameters tellen): Je zou kunnen zeggen: "Ik heb 100 punten nodig om deze heuvel te beschrijven." Als je overstapt op een nieuwe methode, zoals een neuraal netwerk, en zegt: "Ik heb slechts 10 punten nodig," voel je je een winnaar. Je hebt de vloek verslagen!
De Nieuwe Manier (Bits tellen): Maar wacht. Wat als die 10 punten extreem gevoelig zijn? Wat als je, om de vorm van de heuvel accuraat te beschrijven, elk van die 10 punten met extreme precisie moet opslaan—bijvoorbeeld door 1.000 bits voor elk punt nodig te hebben? Plotseling gebruik je niet 10 eenheden aan informatie; je gebruikt 10.000. Ondertussen gebruikte de "oude" methode 100 punten, maar had elk punt slechts 10 bits nodig. Uiteindelijk gebruikte de "oude" methode eigenlijk minder totale bits.

De paper betoogt dat we voor een lange tijd zijn misleid door de "parametercount". We zagen dat neurale netwerken minder knoppen gebruikten en namen aan dat ze efficiënter waren. Maar toen de auteurs de efficiëntie maten in termen van bits (de werkelijke valuta van berekening), veranderde het verhaal.

De "Magie" die niet zo Magisch is

De onderzoekers keken naar twee belangrijke soorten "magie" waar neurale netwerken beroemd om waren:

Dimensie-onafhankelijke Snelheden: Sommige studies beweerden dat neurale netwerken bepaalde complexe functies konden benaderen zonder dat hun prestaties verslechterden naarmate het aantal dimensies toenam. Het klonk alsof ze een manier hadden gevonden om de omvang van het probleem volledig te negeren.
Superconvergentie: Dit is het idee dat diepe neurale netwerken (netwerken met veel lagen) gladde functies veel sneller kunnen benaderen dan traditionele methoden zoals polynomen of eindige elementen. Het leek erop dat ze de concurrentie voorbij raasden.

Het onderzoek van de auteurs onthulde dat deze "superkrachten" grotendeels een illusie zijn, gecreëerd door de manier waarop we dingen meten.

Wanneer zij de metrische entropie analyseerden—een chique term voor de intrinsieke complexiteit van de functieklasse die wordt benaderd—vonden zij dat de functies die neurale netwerken goed kunnen benaderen (zoals die in "Barron-ruimtes") in werkelijkheid gewoon eenvoudiger zijn dan de functies waar traditionele methoden mee worstelen. Het is niet dat het neurale netwerk een betere kunstenaar is; het is dat het schilderij dat het gevraagd wordt te kopiëren, minder gedetailleerd is dan het schilderij dat de traditionele kunstenaar probeerde te kopiëren. De "dimensie-onafhankelijke" snelheid komt niet doordat het netwerk speciaal is; het komt doordat het doelwit in de basis al makkelijk was.

De Diepe Netwerk Valstrik

De meest verrassende bevinding heeft betrekking op diepe neurale netwerken. Dit zijn de netwerken met vele lagen die de meeste aandacht hebben gekregen. De paper laat zien dat hoewel diepe netwerken inderdaad een snellere foutmarge kunnen bereiken wanneer gemeten aan de hand van het aantal parameters (de "knoppen"), deze snelheid gepaard gaat met een verborgen belasting.

Omdat diepe netwerken zo complex en gevoelig zijn, moeten de getallen binnenin hen (de gewichten en biases) met veel hogere precisie worden opgeslagen om fouten te voorkomen. De auteurs bewezen dat het aantal bits dat nodig is om deze parameters op te slaan, explosief groeit naarmens het netwerk dieper wordt.

Denk hierbij aan het volgende: een ondiep netwerk is als een stevige houten brug. Het vereist veel planken (parameters), maar elke plank is gemakkelijk te meten en op te slaan. Een diep netwerk is als een glazen brug. Het gebruikt minder planken, maar elke plank is zo fragiel en precies dat je een laser scanner nodig hebt om hem te meten. Als je probeert een glazen brug te bouwen met een standaard meetlint (eindige precisie), stort deze in.

De paper demonstreert dat wanneer je de totale bits telt die nodig zijn om die glazen brug te bouwen, de "efficiëntie" verdwijnt. De extra bits die nodig zijn om het diepe netwerk stabiel te houden, heffen het voordeel van het hebben van minder parameters op. Sterker nog, voor veel standaardproblemen vereisen diepe netwerken uiteindelijk net zoveel bits, of zelfs meer, dan klassieke methoden zoals polynomen of eindige elementen.

Het Vonnis: Het is een Beetje een Vloek

Dus, verslaan neurale netwerken de vloek van de dimensionaliteit? Volgens Mao en Xu is het antwoord nee, althans niet op de manier die we dachten.

De "vloek" gaat niet echt over het aantal dimensies. Het gaat over de bitcomplexiteit. De fundamentele limiet van hoe goed je een functie kunt benaderen, wordt bepaald door hoeveel informatie (bits) die functie daadwerkelijk bevat. Dit wordt beheerst door "metrische entropie".

Als een functie complex is, zijn er veel bits nodig om deze te beschrijven, ongeacht welke tool je gebruikt.
Als een functie simpel is, zijn er minder bits nodig.

Neurale netwerken veranderen de regels van het spel niet; ze veranderen alleen de manier waarop we de score bijhouden. Wanneer we het spel bekijken door de lens van bits in plaats van parameters, verdwijnt de "superieuriteit" van neurale netwerken vaak. De schijnbare voordelen, zoals dimensie-onafhankelijke snelheden of superconvergentie, komen vaak voort uit het feit dat de neurale netwerken worden getest op functieklassen die inherent minder complex zijn (een lagere metrische entropie hebben) dan de klassen waarop traditionele methoden worden getest.

Waarom dit ertoe doet

Deze paper zegt niet dat neurale netwerken nutteloos zijn. Het zegt dat we slimmer moeten zijn in hoe we ze evalueren. In de echte wereld hebben computers een eindig geheugen. Ze kunnen geen oneindige precisie opslaan. Als een methode op papier geweldig lijkt omdat hij minder parameters gebruikt, maar een enorme hoeveelheid geheugen vereist om die parameters accuraat op te slaan, is het misschien niet de beste keuze voor een real-world toepassing.

De auteurs suggereren dat de "vloek van de dimensionaliteit" eigenlijk een "vloek van de bitcomplexiteit" is. De echte limiet is niet hoeveel dimensies je hebt, maar hoeveel bits je nodig hebt om het probleem te beschrijven. Door onze focus te verleggen van het tellen van knoppen naar het tellen van bits, krijgen we een veel helderder, realistischer beeld van wat deze krachtige instrumenten wel en niet kunnen. Het is een herinnering dat in de wereld van de hoogdimensionele wiskunde de duivel altijd in de details zit—en die details worden gemeten in bits.

Technische Samenvatting: Verslaan Neurale Netwerken Echt de Vloek van de Dimensionaliteit? Een Perspectief vanuit Bit-Complexiteit

1. Probleemstelling

Hoogdimensionale benadering is een centrale uitdaging in de wetenschappelijke berekeningen en machine learning, die traditioneel wordt gehinderd door de "vloek van de dimensionaliteit" (curse of dimensionality). In de klassieke benaderingstheorie groeit het aantal vrijheidsgraden ( $N$ ) dat vereist is om een voorgeschreven nauwkeurigheid te bereiken, vaak exponentieel met de dimensie ( $d$ ). Bijvoorbeeld, in Sobolev-ruimtes $H^r([0,1]^d)$ schaalt de optimale convergentiesnelheid voor klassieke methoden (polynomen, eindige elementen) als $O(N^{-r/d})$ , waarbij de exponent verslechtert naarmate $d$ toeneemt.

Recente literatuur suggereert dat neurale netwerken (zowel ondiepe als diepe) deze vloek kunnen overwinnen door dimension-onafhankelijke rates of "superconvergentie" te vertonen (bijvoorbeeld het bereiken van $O(N^{-2r/d})$ voor diepe ReLU-netwerken in Sobolev-ruimtes). Deze resultaten worden echter doorgaans gemeten in termen van het aantal parameters ( $N$ ).

Het artikel identificeert een kritische kloof: praktische berekeningen opereren onder een eindige precisie. Parameters moeten worden gecodeerd met een eindig aantal bits. De auteurs stellen dat het meten van efficiëntie uitsluitend op basis van het aantal parameters misleidend is, omdat het de bit-complexiteit negeert die nodig is om die parameters met voldoende nauwkeurigheid te representeren. Het centrale probleem is om benaderingsrates opnieuw te evalueren door de lens van computationele bit-complexiteit en metrische entropie om te bepalen of neurale netwerken werkelijk een intrinsïem voordeel hebben ten opzichte van klassieke methoden.

2. Methodologie

De auteurs ontwikkelen een verenigd benaderingskader gebaseerd op binaire codering en metrische entropie.

2.1 Metrische Entropie en Bit-Complexiteit

Het kerninstrument van de theorie is de metrische entropie (of dyadische entropienummer) $\epsilon_m(K)_X$ , gedefinieerd als de minimale straal $\epsilon$ waarvoor een compacte verzameling $K$ in een Banach-ruimte $X$ bedekt kan worden door $2^m$ bollen van straal $\epsilon$ .

Propositie 2 stelt vast dat $\epsilon_m(K)_X$ kwantitatief equivalent is aan de optimale benaderingsfout die haalbaar is met $m$ bits. Zo karakteriseert metrische entropie de intrinsieke informatie-inhoud (bit-complexiteit) van een functieklasse.
Het artikel maakt onderscheid tussen parameter-gebaseerde rates (convergentie in termen van $N$ ) en bit-gebaseerde rates (convergentie in termen van $N_b$ , het totaal aantal bits).

2.2 Coderinganalyse

De methodologie behelst het analyseren van hoe klassieke en neurale netwerkbenaderingen vertalen naar eindige-bit representaties:

Parameterrepresentatie: Een benaderingsmethode brengt een functie $f$ in kaart naar een verzameling parameters $\Theta \in \mathbb{R}^N$ .
Kwantisering: Parameters worden gekwantiseerd naar $\tau$ bits elk, wat resulteert in een totaal bitbudget $N_b = N\tau$ .
Stabiliteitsanalyse: De auteurs analyseren de Lipschitz-constante (gevoeligheid) van de reconstructie-afbeelding $\tilde{S}_N$ . Als de reconstructie zeer gevoelig is voor parameterperturbaties, is een grotere $\tau$ (meer bits per parameter) vereist om een specifieke fouttolerantie te handhaven.
Ondergrenzen: Met behulp van Lemma 2 leidt het artikel ondergrenzen af voor benaderingsfouten op basis van het verschil tussen de metrische entropie van de doel-functieklasse en de metrische entropie van de benaderingsklasse.

3. Belangrijkste Bijdragen en Resultaten

3.1 Klassieke Methoden (Polynomen, FEM, Sparse Grids)

Het artikel analyseert klassieke methoden (polynoombenadering, eindige elementen, sparse grids) binnen het bit-complexiteitskader.

Resultaat: Voor klassieke methoden die Sobolev-ruimtes $H^r$ benaderen, is de parameter-gebaseerde rate $O(N^{-r/d})$ . Wanneer dit wordt omgezet naar bit-gebaseerde rates, wordt de convergentie $O((N_b / \log N_b)^{-r/d})$ .
Suboptimaliteit: De auteurs tonen aan dat deze methoden over het algemeen suboptimaal zijn ten opzichte van de intrinsieke metrische entropielimieten van de functieklassen. De metrische entropie van $H^r$ vervalt als $m^{-r/d}$ , maar klassieke methoden falen vaak om deze rate te bereiken wanneer bit-beperkingen in overweging worden genomen, met name door de logaritmische overhead bij het coderen van parameters.

3.2 Neurale Netwerken: Ondiepe en Diepe Netwerken

Het artikel evalueert opnieuw de prestaties van neurale netwerken (ReLU en ReLU $^k$ ) op Barron-ruimtes en Sobolev-ruimtes.

Ondiepe Netwerken op Barron-ruimtes:
- Ondiepe netwerken bereiken parameter-gebaseerde rates van $O(N^{-1/2 - (2k+1)/2d})$ op Barron-ruimtes.
- Bit-complexiteitsperspectief: Wanneer rekening wordt gehouden met bit-codering, blijft de rate vergelijkbaar met de metrische entropie van de Barron-ruimte. De "dimension-onafhankelijke" verschijning wordt toegeschreven aan de lage metrische entropie van de Barron-ruimte zelf, en niet aan een architecturaal superieur vermogen. De doelklasse is simpelweg minder complex dan de Sobolev-ruimte.
Diepe Netwerken en Superconvergentie:
- Er is aangetoond dat diepe ReLU-netwerken "superconvergentie"-rates van $O(N^{-2r/d})$ kunnen bereiken in Sobolev-ruimtes, wat de exponent vergeleken met klassieke methoden schijnbaar verdubbelt.
- Bit-complexiteitsperspectief: De auteurs demonstreren dat deze verbetering een artefact is van het tellen van parameters. Lemma 1 bewijst dat de reconstructie-afbeelding voor diepe netwerken een exponentiële gevoeligheid vertoont voor parameterperturbaties (de Lipschitz-constante groeit als $(n+1)(W+1)^{n+1}M^{n+1}$ ).
- Om dezelfde nauwkeurigheid te behouden, moet de vereiste precisie (bits per parameter) polynomiaal groeien met de netwerkgrootte. Bij consequentie degradeert de bit-gebaseerde rate voor diepe netwerken naar $O(N_b^{-2r/3d})$ (of vergelijkbaar, afhankelijk van constanten), wat de klassieke $O(N_b^{-r/d})$ rate niet overtreft. De "superconvergentie" wordt tenietgedaan door de enorme bitkosten die nodig zijn voor een stabiele representatie met eindige precisie.

3.3 Ondergrenzen en Optimaliteit

Met behulp van het metrische entropiekader stelt het artikel fundamentele ondergrenzen vast:

Geen enkele methode kan fundamenteel de benaderingsorde overtreffen die wordt bepaald door de metrische entropie van de doel-functieklasse.
Veel schijnbare voordelen van neurale netwerken (dimension-onafhankelijkheid, superconvergentie) komen voort uit het analyseren van functieklassen met lagere intrinsieke complexiteit (bijv. Barron-ruimtes) of het negeren van de bitkosten van stabiliteit (in het geval van diepe netwerken).

4. Betekenis en Conclusies

Het artikel concludeert dat de "vloek van de dimensionaliteit" geen intrinsiek kenmerk is van hoogdimensionale benadering, maar eerder een vloek van de bit-complexiteit die wordt beheerst door metrische entropie.

Herformulering van de Vloek: De fundamentele beperking is niet de dimensie $d$ zelf, maar de metrische entropie van de te benaderen functieklasse. Als een functieklasse een lage metrische entropie heeft (zoals Barron-ruimtes), kan deze efficiënt worden benaderd ongeacht de dimensie.
Beperkingen van Neurale Netwerken: Neurale netwerken bezitten geen intrinsiek architecturaal voordeel waarmee ze de limieten die door metrische entropie worden gesteld, kunnen omzeilen.
- Hun succes op specifieke klassen (Barron) komt door de lage complexiteit van die klassen.
- Hun "superconvergentie" in diepe netwerken is een illusie van parameter-telling die verdwijnt wanneer beperkingen van eindige precisie (bit-complexiteit) worden toegepast.
Praktische Implicatie: In praktische berekeningen met eindige precisie is de bit-kost van het representeren van parameters de werkelijke bottleneck. Methoden die superieur lijken in parameter-aantal, kunnen inferieur zijn in bit-complexiteit vanwege instabiliteit.

De auteurs stellen dat een verenigd perspectief gebaseerd op metrische entropie en bit-complexiteit een accuratere en realistischere benchmark biedt voor het evalueren van benaderingsmethoden, waarbij wordt aangetoond dat traditionele klassieke methoden en neurale netwerken onderworpen zijn aan dezelfde fundamentele informatie-theoretische limieten.