On Minimal Depth in Neural Networks

Dit artikel introduceert een geometrisch raamwerk voor dieptecomplexiteit van convexe polytopen om de expressiviteit van ReLU-netwerken te analyseren, waarbij wordt bewezen dat hoewel $\lceil \log_2(n+1)\rceil$ lagen voldoende zijn voor algemene continue stuksgewijs lineaire functies, Input Convex Neural Networks (ICNNs) geen universele dieptegrens hebben voor het representeren van alle convexe functies.

De kern

Titel: Hoe diep moet je graven? Een verhaal over de "diepte" van neurale netwerken

Stel je voor dat een neuraal netwerk (de hersenen van een computer) een enorme, ingewikkelde machine is die moet leren om patronen te herkennen. Deze machine is opgebouwd uit lagen, net als een toren. Hoe hoger de toren (hoe meer lagen), hoe complexere taken de machine kan uitvoeren.

Deze paper van Juan L. Valerdi onderzoekt een fundamentele vraag: Hoe hoog moet die toren eigenlijk zijn om een specifieke taak te kunnen doen? En belangrijker nog: zijn er taken die je nooit kunt doen, hoe hoog je de toren ook bouwt, als je bepaalde regels volgt?

Hier is de uitleg in simpele taal, met wat creatieve vergelijkingen.

1. De Bouwstenen: Legoblokken en Schuine Daken

Om dit te begrijpen, moeten we eerst kijken naar wat een computer eigenlijk "ziet".

• ReLU-netwerken: Dit zijn de standaard-neurale netwerken. Ze kunnen vormen maken die eruitzien als een reeks schuine daken en vlakken. In de wiskunde noemen we dit "convexe veelvlakken" (denk aan een diamant of een doosje).
• Diepte (Depth): Dit is het aantal lagen in je toren.
  • 1 laag: Je kunt een simpele lijn of een vlak maken.
  • 2 lagen: Je kunt een hoek of een piramide maken.
  • Meer lagen: Je kunt steeds complexere vormen bouwen, alsof je met Legoblokken een kasteel bouwt.

De auteur introduceert een nieuw meetinstrument: De "Diepte-complexiteit".
Stel je voor dat je een vorm wilt bouwen. Je mag twee dingen doen:

1. Samenvoegen (Minkowski som): Je plakt twee vormen tegen elkaar (zoals twee deegballen die samensmelten).
2. Omhullen (Convex hull): Je neemt een elastiekje en span je het om een groep vormen heen om de buitenste vorm te krijgen.

De "diepte" is het aantal keren dat je deze twee stappen moet afwisselen om je eindvorm te krijgen.

• Een enkel punt? Diepte 0.
• Een lijn (samenvoegen van punten)? Diepte 1.
• Een driehoek (omhullen van lijnen)? Diepte 2.

2. De Grootte van de Toren: Hoe hoog is nodig?

De paper beantwoordt twee grote vragen:

Vraag 1: Hoe hoog moet een standaard-neuraal netwerk zijn om alles te kunnen?
Het blijkt dat er een "magische formule" is. Als je een netwerk hebt met $n$ invoer-variabelen (bijvoorbeeld pixels in een foto), dan heb je maximaal $\lceil \log_2(n + 1) \rceil$ lagen nodig om elke mogelijke vorm te maken.

• De analogie: Stel je hebt een doos met 100 verschillende Lego-stukjes. Je hoeft niet een toren van 100 verdiepingen te bouwen om ze allemaal te kunnen sorteren. Met een slimme stapeling (logaritmisch) kun je het met veel minder lagen doen. De paper bewijst dit wiskundig door te kijken naar hoe de vormen (polytopes) zijn opgebouwd.

Vraag 2: Zijn er vormen die je nooit kunt maken, hoe hoog je ook bouwt?
Hier komt het verrassende deel.
Er bestaat een speciale soort netwerk genaamd ICNN (Input Convex Neural Networks). Deze netwerken zijn "disciplinair": ze mogen alleen vormen maken die convex zijn (zoals een bol of een kubus, maar nooit een holle kom of een maanvorm).

• Voor standaard netwerken is er een vaste limiet aan de hoogte die nodig is.
• Voor deze "disciplinaire" ICNN-netwerken is er geen limiet.

De analogie van de Cyclische Polytoop:
De auteur kijkt naar een specifieke vorm genaamd een "cyclische polytoop". Stel je voor dat je deze vorm bouwt met steeds meer hoekpunten (vertices).

• Bij een standaard netwerk kun je deze vorm altijd maken met een redelijke torenhoogte.
• Bij een ICNN-netwerk: hoe meer hoekpunten je toevoegt, hoe dieper de toren moet worden. Als je de vorm oneindig complex maakt, moet je toren oneindig hoog worden. Er is dus geen "maximale hoogte" die voor alle vormen werkt.

3. Waarom is dit belangrijk?

Dit onderzoek is als het vinden van de "bouwregels" voor de toekomstige AI.

1. Efficiëntie: We weten nu precies hoe hoog een standaard AI-toren moet zijn om een taak te voltooien. We hoeven niet blindelings enorme netwerken te bouwen als een kleiner, slimmer netwerk volstaat.
2. Beperkingen van speciale AI: Veel mensen gebruiken ICNN's omdat ze "veilig" zijn (ze gedragen zich voorspelbaar). Deze paper waarschuwt echter: "Pas op! Als je te complexe vormen wilt maken met deze veilige AI, moet je je toren oneindig hoog maken. Dat is onmogelijk in de praktijk." Er is dus een scherpe grens tussen wat een standaard AI kan en wat een "veilige" AI kan.

Samenvatting in één zin:

De paper laat zien dat voor standaard neurale netwerken er een vaste, berekenbare "maximale hoogte" is om elke vorm te maken, maar dat voor speciale, veiligere netwerken (ICNN's) deze hoogte oneindig kan worden naarmate de vorm complexer wordt – alsof je probeert een kasteel te bouwen met Legoblokken die je alleen mag stapelen in één specifieke richting; hoe groter het kasteel, hoe langer je ladder moet zijn, en die ladder heeft geen plafond.

Technische samenvatting

Titel: Over Minimale Diepte in Neuronale Netwerken

Auteur: Juan L. Valerdi
Onderwerp: Theoretisch Deep Learning, Meetkunde van Convexe Polytopen, Expressiviteit van ReLU-netwerken.

---

1. Probleemstelling

Een centraal probleem in de theorie van deep learning is het begrijpen van de relatie tussen de diepte van een neurale netwerk (aantal verborgen lagen) en zijn expressiviteit (het vermogen om bepaalde functies te representeren).

• ReLU-netwerken genereren continue stuksgewijs lineaire (CPWL) functies.
• Een fundamentele vraag is: Wat is de minimale diepte $m$ die nodig is om elke CPWL-functie in $\mathbb{R}^n$ te representeren?
• Bestaande resultaten (Arora et al., 2018) tonen aan dat $\lceil \log_2(n+1) \rceil$ lagen voldoende zijn. Er is echter een conjectuur dat dit de exacte ondergrens is voor de functie $\max\{x_1, \dots, x_n, 0\}$.
• Een specifiek sub-probleem betreft Input Convex Neural Networks (ICNNs). Hoewel deze netwerken alle convexe CPWL-functies kunnen representeren, is onduidelijk of er een universele dieptegrens bestaat die onafhankelijk is van het aantal vertices in de functie.

2. Methodologie: Meetkundige Framework

Valerdi introduceert een meetkundig raamwerk om de expressiviteit van ReLU-netwerken te analyseren via het concept van dieptecomplexiteit van polytopen ($d(P)$).

• Dieptecomplexiteit ($d(P)$): Een recursieve maatstaf voor de complexiteit van een convex polytoop $P$.
  • $d(P) = 0$ als $P$ een enkel punt is.
  • $d(P) = m$ is het kleinste positieve gehele getal zodanig dat $P$ kan worden geconstrueerd door een afwisseling van convexe hulls ($\text{conv}$) en Minkowski-sommen ($+$) van polytopen met diepte $< m$.
  • Formeel: $P = \sum_{i=1}^q \text{conv}(P_{i1}, P_{i2})$ met $d(P_{ij}) < m$.
• Isomorfisme: Er wordt gebruik gemaakt van de isomorfisme tussen de semiring van lineaire max-functies (met $\max$ en $+$) en de semiring van convexe polytopen (met $\text{conv}$ en Minkowski-som).
  • Een functie $f(x) = \max\{a_1 \cdot x, \dots, a_p \cdot x\}$ correspondeert met een Newton-polytoop $N_f = \text{conv}(a_1, \dots, a_p)$.
• Koppeling aan Netwerken: Volgens Theorema 2 (Hertrich et al.) kan een positief homogene CPWL-functie $f$ worden gerepresenteerd door een ReLU-netwerk van diepte $m$ dan en slechts dan als de Newton-polytoop van de componenten van $f$ een dieptecomplexiteit $d(P) \leq m$ heeft.

3. Belangrijkste Bijdragen en Resultaten

A. Boven- en Ondergrenzen voor Dieptecomplexiteit

De auteur leidt strikte grenzen af voor $d(P)$ op basis van de structuur van het polytoop:

• Bovenlimieten: Gebaseerd op het aantal vertices ($f_0$), randen ($f_1$) en 2-vlakken ($f_2$). Voor een polytoop met $k$ vertices geldt $d(P) \leq \lceil \log_2 k \rceil$.
• Onderlimieten: Gebaseerd op de graafstructuur (1-skelet) van het polytoop.
  • Stelling 5: Als de graaf $G(P)$ een volledige subgraaf (clique) bevat met $k$ vertices, dan geldt $d(P) \geq \lceil \log_2 k \rceil$.
  • Dit volgt uit het feit dat volledige subgrafen zich "propageren" door de Minkowski-som en convexe hull operaties.

B. Diepte van Specifieke Polytopen Families

De paper analyseert de diepte van verschillende klassen van polytopen:

1. Simplices: Voor een $n$-simplex (met $n+1$ vertices) is de diepte exact $\lceil \log_2(n+1) \rceil$.
   • Consequentie: Dit levert een puur meetkundig bewijs op voor de expressiviteitsgrens van Arora et al. (2018), bevestigend dat $\lceil \log_2(n+1) \rceil$ lagen voldoende zijn voor elke CPWL-functie.
2. Cyclische Polytopen ($C_n(k)$): Voor dimensies $n \geq 4$ zijn cyclische polytopen met $k$ vertices 2-buurlijk (elk paar vertices vormt een rand).
   • Resultaat: $d(C_n(k)) = \lceil \log_2 k \rceil$.
   • Cruciaal Inzicht: In tegenstelling tot simplices, groeit de diepte van cyclische polytopen onbeperkt naarmate het aantal vertices $k$ toeneemt. Er bestaat dus geen universele bovengrens voor de diepte van polytopen in hoge dimensies.

C. Implicaties voor Input Convex Neural Networks (ICNNs)

Dit is een van de belangrijkste bevindingen van het artikel:

• ICNNs zijn beperkt tot het gebruik van convexe operaties (geen aftrekking van functies, zoals bij standaard ReLU-netwerken).
• De auteur definieert een specifieke dieptecomplexiteit $d_0(P)$ voor ICNNs.
• Omdat $d(P) \leq d_0(P)$ en cyclische polytopen een onbeperkt groeiende diepte hebben voor $n \geq 4$, volgt hieruit dat ICNNs geen universele dieptegrens hebben.
• Conclusie: Er bestaat geen vast aantal lagen $m$ dat voldoende is om alle convexe CPWL-functies te representeren met een ICNN. Dit vormt een scherpe scheiding in expressiviteit tussen standaard ReLU-netwerken (die wel een universele grens hebben) en ICNNs.

D. Constructie van Polytopen met Vaste Diepte

De auteur toont aan dat voor $n \geq 5$ en elke gewenste diepte $m$, er families van polytopen bestaan met willekeurig veel vertices die allemaal diepte $m$ hebben. Dit wordt bereikt door de Minkowski-som van een polytoop met diepte $m$ en een zonotoop (diepte 1) te nemen.

4. Significatie en Conclusie

• Theoretische Verduidelijking: Het artikel biedt een rigoureuze meetkundige onderbouwing voor bestaande resultaten over de diepte van ReLU-netwerken en lost de conjectuur over de minimale diepte voor simplices op.
• Fundamentele Beperking ICNNs: Het weerlegt de aanname dat ICNNs, ondanks hun vermogen om convexe functies te representeren, efficiënt (met vaste diepte) kunnen worden opgeschaald voor complexe convexe functies in hoge dimensies.
• Nieuw Instrument: De introductie van "dieptecomplexiteit van polytopen" als een meetkundige maatstaf biedt een krachtig nieuw hulpmiddel voor het analyseren van de expressiviteit van neurale netwerken, los van de specifieke netwerkarchitectuur.

Samenvattend beweert Valerdi dat de meetkundige complexiteit van de doelwitfunctie (gevisualiseerd als een polytoop) de fundamentele limiet is voor de diepte van het netwerk dat deze functie moet representeren, en dat deze limieten fundamenteel verschillen tussen standaard ReLU-netwerken en convexe varianten (ICNNs).