Geometry-Aware Probabilistic Circuits via Voronoi Tessellations

Deze paper introduceert een nieuwe aanpak voor probabilistische circuits die Voronoï-tessellaties gebruikt om de lokale geometrie van data te modelleren, en lost het hieruit voortvloeiende verlies van berekenbaarheid op door zowel een benaderend inferentiekader met gegarandeerde grenzen als een structurele voorwaarde voor exacte, tractabele inferentie te ontwikkelen.

De kern

Stel je voor dat je een super-intelligente voorspeller bouwt die de wereld probeert te begrijpen. Deze voorspeller heet een "Probabilistic Circuit" (PC). Zijn kracht is dat hij niet alleen goede voorspellingen doet, maar ook precies weet hoe zeker hij is van die voorspelling. Hij kan razendsnel rekenen, zelfs bij complexe vraagstukken.

Maar er is een probleem: deze voorspeller is een beetje stijf. Hij gebruikt vaste regels voor iedereen. Of je nu een klein kind bent of een oude man, hij behandelt je precies hetzelfde. Hij ziet niet dat de wereld lokaal anders werkt. In de ene buurt zijn de regels anders dan in de andere.

De auteurs van dit paper zeggen: "Laten we deze voorspeller een paar ogen geven, zodat hij de vorm van de wereld echt kan zien." Ze noemen dit Voronoi Tessellations.

Hier is de uitleg in gewone taal, met een paar leuke metaforen:

1. Het Probleem: De Stijve Chef

Stel je een grote fabriek voor (de PC) waar verschillende vakmensen (experts) werken.

• Huidige situatie: Er is een chef die beslist wie er aan het werk gaat. Maar deze chef is een beetje lui. Hij zegt: "Voor 30% van de tijd doen we dit, en voor 70% dat." Het maakt hem niet uit of het product nu een auto is of een fiets. De regels zijn overal hetzelfde.
• Het gevolg: Als de wereld ingewikkeld is (bijvoorbeeld een spiraalvormige weg of een knoop), kan de fabriek dit niet goed nabootsen. Hij mist de lokale details.

2. De Oplossing: De Kaart van de Buurten (Voronoi)

De auteurs willen de chef slimmer maken. In plaats van vaste percentages, wil hij dat de chef kijkt waar het product vandaan komt.

• De Metafoor: Stel je een kaart van een stad voor. Je deelt de stad op in buurten rondom een paar centrale pleinen (centroïden).
  • Als je in de buurt van Plein A woont, ga je naar de experts bij Plein A.
  • Als je bij Plein B woont, ga je naar de experts bij Plein B.
• Dit heet een Voronoi-indeling. Het is een slimme manier om de wereld op te delen in gebieden, zodat elke expert zich kan specialiseren in zijn eigen stukje van de kaart. Dit maakt de voorspeller veel slimmer en flexibeler.

3. Het Grote Obstakel: De Rekenkracht-valkuil

Hier wordt het lastig.

• Het probleem: Als je de stad opdeelt in deze buurten, zijn de grenzen vaak schuin (zoals een hoek van een dak).
• De wiskundige nachtmerrie: Voor onze snelle voorspeller is het heel makkelijk om over rechthoekige gebieden te rekenen (zoals een raster). Maar over schuine, onregelmatige vormen rekenen is voor hem als een olifant proberen te vangen in een mierenhol. Het kost zoveel tijd dat het onmogelijk wordt (wiskundig gezien: "intractable"). Hij raakt de weg kwijt en kan zijn snelle rekenkracht niet meer gebruiken.

4. Twee Slimme Manieren om dit Op te Lossen

De auteurs hebben twee oplossingen bedacht, afhankelijk van wat je nodig hebt:

Oplossing A: De "Schatting met Garantie" (Certified Approximate Inference)

Stel je voor dat je een schatting moet maken van hoeveel water er in een vreemd gevormde vijver zit.

• Je kunt de vijver niet precies meten, maar je kunt wel een doos eromheen bouwen die net iets te groot is (buitenste doos) en een doos die er net iets te klein in past (binnenste doos).
• Je weet dan zeker dat het echte antwoord ergens tussen die twee dozen zit.
• In de paper: Ze vervangen de schuine buurten door rechthoekige dozen. Ze berekenen een onder- en bovengrens. Het is niet 100% exact, maar ze kunnen wiskundig garanderen dat het juiste antwoord tussen die twee grenzen ligt. Zo houden ze de snelheid en betrouwbaarheid, ook al is de vorm van de wereld gekromd.

Oplossing B: De "Perfecte Pasvorm" (Hierarchical Factorized Voronoi)

Stel je voor dat je de stad niet zomaar opdeelt, maar dat je de indeling perfect afstemt op de manier waarop de fabriek werkt.

• In plaats van willekeurige schuine lijnen, deelt de chef de stad op in rechthoekige blokken die precies passen bij de vakmensen in de fabriek.
• Het resultaat: De schuine lijnen zijn weg, de rekenkracht blijft intact, en de voorspeller is weer 100% exact en snel.
• De prijs: Je moet de wereld iets minder flexibel indelen (alleen rechthoeken), maar je wint wel aan snelheid en zekerheid.

5. De Leertruc: Van Zacht naar Hard

Hoe leer je zo'n systeem?

• Het is moeilijk om direct te beslissen: "Jij hoort bij Buurt A!" (dat is een harde beslissing). Computers kunnen daar niet goed mee leren.
• De truc: Ze beginnen met een zachte mist. In het begin is het onduidelijk wie bij welke buurt hoort. Iedereen heeft een kleine kans om bij iedereen te horen.
• Naarmate het systeem leert, wordt de mist steeds dunner (de temperatuur wordt lager). Uiteindelijk wordt het hard: "Jij hoort 100% bij Buurt A!"
• Dit zorgt ervoor dat het systeem stabiel leert, maar op het einde toch die scherpe, snelle beslissingen maakt die we nodig hebben.

Conclusie

Kortom: Deze paper maakt een snelle, betrouwbare AI (de Probabilistic Circuit) slimmer door hem te laten kijken naar de vorm van de data (zoals een kaart met buurten).

• Als de vorm te gek is, geven ze een garantie dat het antwoord binnen een bepaalde marge zit.
• Als de vorm goed past, maken ze het systeem perfect en exact.
• En ze leren het systeem op een slimme manier, van zacht naar hard, zodat het niet vastloopt.

Dit betekent dat we in de toekomst AI-systemen kunnen bouwen die niet alleen snel rekenen, maar ook echt begrijpen hoe de wereld er lokaal uitziet, zonder hun superkracht (snelheid) te verliezen.

Technische samenvatting

Hieronder volgt een gedetailleerde technische samenvatting van het artikel "Geometry-Aware Probabilistic Circuits via Voronoi Tessellations" in het Nederlands.

Probleemstelling

Probabilistische Circuits (PC's) zijn een krachtige klasse van generatieve modellen die exacte en tractabele (berekende) inferentie toestaan, zoals het berekenen van likelihoods, marginals en conditionals in lineaire tijd. Dit wordt mogelijk gemaakt door strikte structurele beperkingen, zoals decomposabiliteit en smoothness.

Echter, een fundamentele beperking van bestaande PC-architecturen is dat de mixture weights (de gewichten bij som-nodes) data-onafhankelijk zijn. Dit betekent dat de routeringsbeslissingen binnen de circuit vast staan en niet adaptief zijn op basis van de invoer. Hierdoor kunnen PC's de lokale geometrische structuur van het data-maandblad (data manifold) niet goed modelleren. Veel realistische verdelingen vertonen stuksgewijs gedrag of lokale afhankelijkheden die niet kunnen worden gemodelleerd met globaal gedeelde gewichten.

De centrale vraag is: Kunnen we geometrie-bewuste, invoer-afhankelijke routering introduceren in PC's zonder de tractabiliteit van de inferentie te verliezen?

Methodologie

De auteurs stellen Voronoi-tessellaties (VT) voor als een natuurlijk mechanisme om geometrische structuur direct in de som-nodes van een PC te integreren. In plaats van vaste gewichten, worden invoerdata toegewezen aan lokale "experts" (subcircuits) op basis van hun afstand tot een set van geleerde centroiden.

Het artikel identificeert echter een fundamenteel conflict:

1. Intractabiliteit: Voronoi-cellen worden gedefinieerd door snijpunten van schuine half-ruimten. Het integreren over deze convexe polyhedra is #P-hard en breekt de recursieve factorisatie die nodig is voor exacte inferentie in PC's, zelfs als de expert-verdelingen zelf volledig gefactoriseerd zijn.

Om dit probleem op te lossen, ontwikkelen de auteurs twee complementaire oplossingen:

1. Gecertificeerde Benaderde Inferentie (Certified Approximate Inference)

Voor het geval dat men de volledige expressiviteit van Voronoi-cellen wil behouden (inclusief schuine grenzen), wordt een raamwerk ontwikkeld dat exacte inferentie vervangt door garandeerde onder- en bovengrenzen.

• Methode: De ingewikkelde Voronoi-cellen worden benaderd door tractabele, as-uitgelijnde dozen (axis-aligned boxes).
  • Een inner box (binnenbox) ligt volledig binnen de Voronoi-cel.
  • Een outer box (buitenbox) omvat de Voronoi-cel.
• Propagatie: Deze box-benaderingen worden door het circuit gepropageerd. Voor product-nodes worden de grenzen vermenigvuldigd, en voor som-nodes worden ze opgeteld.
• Refinement: Een adaptief algoritme (Algorithm 1) splitst de "boundary boxes" (grensdozen) recursief op om de kloof tussen de onder- en bovengrens te verkleinen, waardoor de nauwkeurigheid willekeurig dicht bij de exacte waarde kan komen.

2. Hiërarchisch Gefactoriseerde Voronoi PC's (HFV-PCs)

Voor het geval exacte tractabiliteit vereist is, wordt een structurele voorwaarde geïntroduceerd: Geometrische Alignering.

• Principe: De Voronoi-tessellatie wordt gefactoriseerd op een manier die overeenkomt met de decompositie van het circuit (de vtree-structuur).
• Implementatie: In plaats van één hoge-dimensionale Voronoi-cel, worden er onafhankelijke Voronoi-cellen gedefinieerd voor elke subset van variabelen die door een product-node wordt gescheiden. De gezamenlijke cel is het Cartesisch product van deze lagere-dimensionale cellen.
• Resultaat: Hierdoor blijven de integrals factoriseerbaar, waardoor exacte en tractabele inferentie wordt hersteld, terwijl er nog steeds sprake is van geometrie-bewuste routering.

Leren via Soft Gating

Omdat harde Voronoi-toewijzingen niet differentieerbaar zijn (wat gradient-based learning blokkeert), introduceren de auteurs een zachte relaxatie:

• Soft Voronoi Gate: Een temperatuur-geschaalde softmax-functie gebaseerd op de afstand tot de centroiden.
• Training: Het model wordt getraind met een hoge temperatuur (zachte routering) en de temperatuur wordt geleidelijk verlaagd (annealing) tijdens het trainingsproces.
• Inferentie: Tijdens de testfase wordt teruggekeerd naar de harde Voronoi-toewijzing, waardoor de exacte inferentie-garanties (bij HFV) of de gecertificeerde grenzen (bij VT) worden hersteld.

Belangrijkste Bijdragen

1. Eerste geometrische aanpak voor PC's: Het introduceren van Voronoi-tessellaties als mechanisme voor data-afhankelijke routering in probabilistische circuits.
2. Formalisatie van incompatibiliteit: Het aantonen dat onbeperkte geometrische routering de tractabiliteit breekt en het bieden van twee oplossingsrichtingen: gecertificeerde benadering en hiërarchische factorisatie.
3. Theoretische analyse: Het bewijzen van de convergentie van de zachte naar de harde gating en het analyseren van de complexiteit en convergentie van de benaderde inferentie.
4. Empirische validatie: Succesvolle toepassing op synthetische 2D en 3D datasets met complexe geometrische structuren (zoals spiralen, knopen en verstrengelde cirkels).

Resultaten

De auteurs hebben hun methode getest op acht synthetische datasets (4x 2D, 4x 3D) en vergeleken met state-of-the-art baselines (zoals EinsumNet en HCLT).

• Expressiviteit: De VT-modellen (met gecertificeerde benaderde inferentie) presteerden consistent beter dan de baselines. Zelfs de ondergrens van de log-likelihood was vaak hoger dan de exacte likelihood van de baselines, wat aantoont dat de geometrische expressiviteit cruciale structuren vangt die door data-onafhankelijke gewichten worden gemist.
• Exacte Tractabiliteit: De HFV-modellen bereikten prestaties vergelijkbaar met de baselines, maar behielden de garantie van exacte inferentie. Hoewel ze in lage dimensies iets minder expressief kunnen zijn door de aligneringsbeperkingen, bieden ze een interpreteerbare en wiskundig veilige alternatief.
• Visualisatie: De resultaten tonen aan dat VT-modellen de routering kunnen aanpassen aan de lokale vorm van de data (bijv. de armen van een pinwheel-distributie), terwijl HFV-modellen hiërarchische, as-uitgelijnde regio's gebruiken die de decomposabiliteit respecteren.

Significantie

Dit werk is significant omdat het een brug slaat tussen de wereld van tractabele probabilistische modellen (die betrouwbaar zijn voor inferentie) en diepe generatieve modellen (die flexibel zijn in het modelleren van complexe geometrie).

• Het lost het dilemma op tussen expressiviteit en tractabiliteit door ofwel garandeerde grenzen te bieden (voor onbeperkte geometrie) ofwel structurele beperkingen op te leggen die exacte inferentie mogelijk houden.
• Het opent de deur voor toepassingen die geometrische interpretatie vereisen, zoals continue learning (waar nieuwe gebieden in de ruimte kunnen verschijnen), controleerbare generatie, en interpretable anomaly detection.
• De methode biedt een fundamentele theoretische basis voor het ontwerpen van probabilistische circuits die adaptief zijn op de lokale structuur van de data, zonder in te leveren op de betrouwbaarheid van de inferentie.