The information-theoretic complexity of differentiable functions

Technische Samenvatting: De Informatietheoretische Complexiteit van Differentieerbare Functies

Probleemstelling
Het artikel behandelt de moeilijkheid om een rigoureuze maatstaf te definiëren voor de complexiteit van differentieerbare functies $f: [a, b] \to \mathbb{R}$. Hoewel complexiteit een alomtegenwoordig concept is in systemen variërend van klimaatmodellen tot cellulaire automata, ontbreekt er een verenigde definitie. De auteur stelt dat complexiteit moet corresponderen met de hoeveelheid informatie die nodig is om een object te beschrijven. Aangezien differentieerbare functies oneindige informatie bevatten, stelt het artikel voor om complexiteit te definiëren op basis van eindige benaderingen. De kernintuïtie is dat een functie "simpel" is als een goede benadering met weinig parameters kan worden beschreven, en "complex" als er veel parameters voor nodig zijn. Het artikel onderzoekt specifiek de relatie tussen visuele eenvoud (waargenomen door het menselijk oog als scherpe contrasten en contouren) en informatietheoretische maatstaven.

Methodologie
Het artikel introduceert een maatstaf genaamd V-complexiteit, afgeleid van het benaderen van een differentieerbare functie $f$ met behulp van stuksgewijs constante functies (stapfuncties). De methodologie verloopt als volgt:

1. Benaderingskader: De functie $f$ wordt benaderd door een stapfunctie $q$ zodanig dat de $L_1$-norm van het verschil, $||f - q||_1$, kleiner is dan een maximale fout $\epsilon$. De $L_1$-norm wordt gekozen boven andere $L_p$-normen omdat deze overeenkomt met de menselijke visuele perceptie, waarbij de precieze locatie van een scherpe grens (contrast) minder belangrijk is dan het bestaan van het contrast zelf.
2. Equiverdeling van de Fout: Om het aantal intervallen $N(\epsilon)$ te minimaliseren dat nodig is voor een gegeven $\epsilon$, maakt het artikel gebruik van het principe van equiverdeling van de fout. Dit houdt in dat een stapfunctie wordt geconstrueerd waarbij de fout op elk deeltinterval gelijk is ($||f - q_k||_{I_k} = \epsilon/N(\epsilon)$). Het artikel citeert bewijs dat suggereert dat deze methode asymptotisch het minimale aantal intervallen oplevert.
3. Asymptotische Analyse: Door de recursieve berekening van interval-eindpunten om te zetten in een differentiaalvergelijking wanneer $\epsilon \to 0$, leidt het artikel de schalingsrelatie af tussen het aantal intervallen en de fout.
4. Vergelijking met Compressie: Om de V-complexiteit te valideren, vergelijkt het artikel deze met compressie-complexiteit. Dit houdt in dat $f$ wordt gediskretiseerd op een rooster, de waarden worden omgezet in een tekenreeks, en verliesvrije compressie-algoritmen worden toegepast (Run Length Encoding [RLE] en Lempel-Ziv 77 [LZ77/GZIP]). De complexiteit wordt gedefinieerd als het product van de lengte van de gecomprimeerde tekenreeks en de benaderingsfout naarmate de fout naar nul nadert.
5. Toepassing op Complexe Systemen: Het concept wordt toegepast op het "room-in-koffie"-diffusiemodel. Het artikel vergelijkt twee benaderingen:
   • Schijnbare Complexiteit: Het simuleren van het systeem via een roostergas-automaton, het grofkorrelig maken van de output en het meten van de gecomprimeerde lengte.
   • Gewijzigde Effectieve Complexiteit: Het modelleren van het systeem via de diffusievergelijking (een differentieerbare functie) en het berekenen van de V-complexiteit.

Belangrijkste Bijdragen en Resultaten

• Definitie van V-Complexiteit: Het artikel stelt vast dat voor een differentieerbare functie $f$, het aantal intervallen $N(\epsilon)$ dat nodig is voor een $\epsilon-accurate$ stapfunctie-benadering schaalt als $N(\epsilon) \approx V(f)\epsilon^{-1}$ wanneer $\epsilon \to 0$. De voorfactor $V(f)$ wordt gedefinieerd als de V-complexiteit:
  $$V(f) = \frac{1}{4} \left( \int_a^b |f'(x)|^{1/2} dx \right)^2$$
  Deze formule biedt een concrete, analytische maatstaf voor complexiteit gebaseerd op de afgeleide van de functie.

• Gedragsvoorbeelden:

  • Stap-achtige functies: Functies die convergeren naar een stapfunctie (bijvoorbeeld sigmoidfuncties met steile hellingen) hebben een V-complexiteit die naar nul nadert.
  • Oscillerende functies: Voor functies zoals $\cos(n\pi x)$ groeit de V-complexiteit lineair met het aantal oscillaties $n$, wat de toegenomen detailrijkdom weerspiegelt.
  • Vlakke functies: Functies die bijna constant (vlak) zijn, vertonen eveneens een lage V-complexiteit.

• Equivalentie-hypothese: Het artikel hypothesiseert dat V-complexiteit equivalent is aan RLE-complexiteit en bij uitbreiding GZIP-complexiteit (voor monotoone sequenties of in de limiet van kleine roostergroottes). Numerieke simulaties op families van functies (bijvoorbeeld $x^\alpha$) tonen kwalitatieve overeenkomst tussen de analytische V-complexiteit en de empirische compressie-complexiteit.

• Toepassing Diffusiemodel: In het room-in-koffie-model leveren zowel de cellulaire automaton-benadering (Schijnbare Complexiteit) als de diffusievergelijking-benadering (V-complexiteit) hetzelfde kwalitatieve resultaat op: de complexiteit begint bij nul (scheiding), stijgt naar een maximum naarmate het interface mengt en gradiënten creëert, en keert terug naar nul naarmate het systeem een uniforme evenwichtstoestand bereikt.

Betekenis en Beweringen
Het artikel beweert dat V-complexiteit de intuïtie formaliseert dat visuele eenvoud overeenkomt met een lage informatie-inhoud. Het dient als een brug tussen statische, deterministische functie-analyse en de studie van Complexe Systemen.

Specifiek stelt het artikel een wijziging voor in de definitie van Effectieve Complexiteit (EC). Standaard EC wordt gedefinieerd als de lengte van een beknopte beschrijving van de regelmatigheden van een systeem. Echter, als de regelmatigheden worden beschreven door een differentieerbare functie, is de beschrijvingslengte oneindig. Het artikel stelt voor om deze definitie aan te passen: de EC van een systeem waarvan de regelmatigheden worden beschreven door een differentieerbare functie $f$ is simpelweg de V-complexiteit van $f$.

De auteur merkt op dat de equivalentie tussen V-complexiteit en compressie-complexiteit een hypothese blijft die wordt ondersteund door simulaties in plaats van een rigoureus bewijs. Evenzo wordt de aanname dat equiverdeling van de fout het absolute minimale aantal intervallen oplevert, behandeld als een sterke praktische aanname. Het artikel concludeert dat V-complexiteit een veelbelovend hulpmiddel biedt voor het karakteriseren van complexe systemen die worden beschreven door differentieerbare functies, hoewel generalisatie naar meervoudige variabelenfuncties en verdere theoretische verduidelijking worden overgelaten aan toekomstig werk.