Technische Samenvatting: Classificatievelden: Willekeurig fijne recursieve hiërarchische clustering uit enkele voorbeelden

1. Probleemstelling

Klassieke hiërarchische clusteringmethoden werken doorgaans op een vaste, eindige steekproef en leveren ofwel een eindige partitie van de data of een eindig dendrogram op. Deze aanpak is ontoereikend wanneer de onderliggende hiërarchie van belang een recursief geometrisch object is met verfijningen op fijne schaal die verder reiken dan de direct waargenomen niveaus. In dergelijke regimes kan het aantal latente clustercentra ($k$) sterk toenemen ten opzichte van het aantal waargenomen knopen ($N$), en kunnen verfijningen doorgaan op diepten die niet aanwezig zijn in de trainingsdata.

De centrale vraag die dit werk adresseert is: Kunnen we een lokale verfijningsregel leren uit een eindig waargenomen prefix van een hiërarchie en deze recursief toepassen om aanzienlijk diepere, onwaargenomen niveaus te genereren?

Huidige differentieerbare of geleerde benaderingen voor hiërarchie passen doorgaans een eindig waargenomen boom aan, embedden een vaste structuur, of optimaliseren een eindig clusteringdoel. Ze leren geen directe verfijningsmechanisme dat in staat is tot recursieve uitrol buiten de waargenomen hiërarchie.

2. Methodologie: Classificatievelden

De auteurs introduceren Classificatievelden, een meetkundig-geometrisch model voor hiërarchische clustering met oneindige diepte.

2.1 Kerndefinities

• Classificatieveldgenerator (CFG): Een lokale regel $r: \mathbb{R}^d \to (\mathbb{R}^d)^K$ die een oudercentrum afbeeldt op een geordende, begrenste en gescheiden $K$-tupel van kindresiduen.
  • Beperkingen: Voor elke ouder $x$ moeten de kindresiduen $\{r_k(x)\}$ liggen in een Euclidische ring (begrensde norm) en $s_{sep}$-gescheiden zijn.
  • Constructie: CFG's kunnen worden geconstrueerd via orthogonaal-diagonaal-orthogonale vervormingen van een vaste referentiepakking, zodat aan de geometrische beperkingen wordt voldaan.
• Classificatieveld: De hiërarchische structuur met oneindige diepte die wordt verkregen door recursieve toepassing van de CFG, beginnend bij een wortel $x_0$ en een schalingsfactor $s$.
  • Structuur: Het veld is een recursief gegenereerde metrische gerichte acyclische graaf (DAG).
  • Componenten: Het genereert clustercentra, bijbehorende Voronoi-cellen en genealogische adressen.
  • Maten: Het artikel definieert drie afstandsmaten op het veld:
    1. Boommetriek: Gebaseerd op combinatorische kantgewichten (niveaugebonden).
    2. Puntgebaseerde metriek: Gebaseerd op Euclidische afstanden tussen centra.
    3. Celgebaseerde metriek: Gebaseerd op Hausdorff-afstanden tussen Voronoi-cellen, geschaald met de diepte.

2.2 Leren: Classificatieveldpredictors (CFP)

Gegeven een eindig prefix van een hiërarchie (waargenomen tot diepte $L_{train}$), is het doel om een Classificatieveldpredictor (CFP), aangeduid als $\hat{r}$, te leren die de onderliggende CFG benadert.

• Trainingsdoel: Minimaliseren van de kwadratische fout tussen de voorspelde kindresiduen en de waargenomen residuen:
  $$\mathcal{L}(\hat{r} | \mathcal{H}_{train}) = \sum_{l=0}^{L_{train}-1} \sum_{x \in \mathcal{H}_l} \sum_{k=1}^K \| x + s^{l+1}\hat{r}(x)_k - \text{chld}(x)_k \|_2^2$$
• Recursieve Uitrol: Tijdens het testen wordt $\hat{r}$ recursief toegepast vanaf de wortel. Elke gegenereerde kind wordt een ouder voor het volgende niveau. Er worden geen grondwaarheidsknooppunten van onzichtbare niveaus gebruikt tijdens de uitrol.

2.3 Theoretische Garantiën

Het artikel stelt vast dat eindige truncaties van het geleerde veld onder specifieke voorwaarden convergeren naar het voltooide veld met oneindige diepte:

• Exponentiële Convergentie: Onder aannames van begrensdheid, scheiding en regulariteit, neemt de Hausdorff-afstand tussen de truncatie op diepte-$L$ en het voltooide veld exponentieel af met $L$.
• Neurale Realiseerbaarheid: De eindige verfijningsvensters die nodig zijn om de CFG te benaderen, kunnen worden gerealiseerd door ReLU Multi-Layer Perceptrons (MLP's).
  • Complexiteit: De vereiste breedte is $O(\varepsilon^{-\gamma})$ en de diepte is $\tilde{O}(\varepsilon^{-3\gamma/2})$, waarbij $\gamma = \log K / (-\log s)$.
  • Dit bewijst dat een eindig neurale netwerk kan fungeren als een eindig benaderingsmechanisme voor een hiërarchische structuur met oneindige diepte.

3. Experimentele Validatie

De auteurs evalueren de CFP in drie scenario's met toenemende afwijking van de geïdealiseerde theorie:

1. Gekoppelde CFG-gegenereerde Hiërarchieën:

   • Opzet: Data gegenereerd door een bekende CFG uit dezelfde familie als die in de theorie wordt gebruikt.
   • Resultaat: De CFP behoudt de laagste fout op niveau over onzichtbare uitrolhorizonten in vergelijking met baselines (leerbare constante, gemiddeld residu en affiene predictors). Dit bevestigt dat de geleerde lokale regel coherent blijft onder herhaalde zelfcompositie.

2. Out-of-Family IFS Fractale Hiërarchieën:

   • Opzet: Hiërarchieën gegenereerd door Iterated Function Systems (IFS) met gladde niet-lineaire perturbaties (bijv. Sierpiński-driehoek, Cantor-stof, Koch-kromme). Deze hebben een exacte recursieve structuur maar zijn niet getrokken uit de geparametriseerde CFG-familie.
   • Resultaat: De CFP bereikt een lagere MSE, Permutation-Invariante Chamfer-afstand (PI-CD) en dieptevervorming dan baselines. Dit demonstreert dat de formulering van classificatievelden generaliseert buiten de gekoppelde generatorklasse.

3. Beeldgeïnduceerde Recursieve Clustering Hiërarchieën:

   • Opzet: Hiërarchieën geconstrueerd uit CLIP-embeddings van CIFAR-10 en CIFAR-100 afbeeldingen met behulp van een recursieve diepe clusteringmethode. De verfijningsregel is benaderend en kindslots vereisen canonicalisatie (ordening) via PCA.
   • Resultaat: De CFP presteert aanzienlijk beter dan baselines in het behoud van ongeordende geometrie (PI-CD) en padmetrieken op hiërarchieniveau (dpt-vervorming). Dit suggereert dat zelfs in ruwe, real-data scenario's eindige hiërarchie-prefixen leerbare verfijningsmechanismen bevatten.

4. Belangrijkste Bijdragen

1. Conceptueel Kader: Introductie van Classificatievelden als een meetkundig-geometrisch model voor hiërarchische clustering met oneindige diepte, waarbij de focus verschuift van het leren van een hiërarchie over eindige steekproeven naar het leren van een herbruikbare lokale ouder-naar-kind verfijningsregel.
2. Meetkundige Theorie: Ontwikkeling van een rigoureuze meetkundige theorie voor deze objecten, inclusief definities voor boom-, punt- en celgebaseerde afstanden, en kwantitatieve grenzen voor de convergentie van eindige truncaties naar het voltooide veld.
3. Neurale Realiseerbaarheid: Bewijs dat eindige verfijningsvensters kunnen worden gerepresenteerd door ReLU-predictors, waarmee een eindig neurale uitrolmechanisme wordt gevestigd voor het voltooien van hiërarchieën met oneindige diepte, met expliciete complexiteitsgrenzen.

5. Betekenis en Claims

Het artikel claimt dat eindige hiërarchische waarnemingen lokale verfijningsregels kunnen onthullen die in staat zijn om aanzienlijk diepere classificatievelden te genereren. De resultaten ondersteunen het perspectief dat hiërarchische clustering kan worden geformuleerd als het leren van een lokale recursieve verfijningswet, in plaats van het construeren van een eindige combinatorische samenvatting.

De auteurs positioneren dit werk als een complementair perspectief op bestaande methoden voor hiërarchische clustering. Zij wijzen expliciet op beperkingen: het kader gaat uit van een vaste vertakkingsfactor, voldoende scheiding en een herbruikbaar verfijningsproces. Zij erkennen dat het uitbreiden van het kader naar ruwe, variabel vertakkende, zwak uitgelijnde of niet-zelfgelijkende hiërarchieën een belangrijke richting blijft voor toekomstig werk. De experimenten worden gepresenteerd als validatieproeven in plaats van claims dat elk probleem met hiërarchische clustering een perfect classificatieveld toelaat.