📊 statistics

Compositionality in algorithms for smoothing

Dit artikel verbindt het Bidirectionele Filteren en Voorwaartse Leiden (BFFG)-algoritme met optica uit de categorietheorie door aan te tonen dat de voorwaartse en achterwaartse kaarten samen een functor definiëren van een categorie van Markov-kernen naar een categorie van optica.

Oorspronkelijke auteurs: Moritz Schauer, Frank van der Meulen, Andi Q. Wang

Gepubliceerd 2026-03-23

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Moritz Schauer, Frank van der Meulen, Andi Q. Wang

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

De "Twee-Weg" Recept voor Wiskundige Raadsels

Stel je voor dat je een heel ingewikkeld raadsel moet oplossen. Je weet hoe het verhaal begint (de geboorte van een kind) en je ziet het einde (het kind als volwassene), maar je mist alle foto's van het leven in het midden. Je wilt weten: Wat gebeurde er precies op de leeftijd van 10, 15 en 20 jaar?

In de statistiek noemen we dit smoothing (gladstrijken). Het is een probleem dat zich voordoet in alles, van het voorspellen van het weer tot het volgen van een virus.

De auteurs van dit artikel (Moritz, Frank en Andi) hebben een nieuwe manier gevonden om naar dit probleem te kijken. Ze gebruiken een tak van de wiskunde genaamd Categorie-theorie. Klinkt eng? Laten we het vergelijken met LEGO.

1. De LEGO-blokken van de Wiskunde

Stel je voor dat elk stukje van een wiskundig algoritme een LEGO-blok is.

De oude manier: Mensen keken naar het hele bouwwerk als één groot, ondoordringbaar blok. Als je iets wilde veranderen, moest je alles opnieuw bouwen.
De nieuwe manier (deze paper): De auteurs zeggen: "Nee, laten we kijken naar hoe de blokjes aan elkaar klikken." Ze noemen dit compositionaliteit. Als je begrijpt hoe twee blokjes samenwerken, kun je ze in elke volgorde en in elke combinatie gebruiken.

2. De "Twee-Weg" Bus (BFFG)

Het algoritme waar ze over praten, heet BFFG (Backward Filtering Forward Guiding). De naam klinkt als een raadsel, maar het is eigenlijk een bus die twee keer rijdt:

De Terugrit (Backward Filtering): De bus rijdt eerst van het einde naar het begin. Hierbij verzamelt hij informatie over wat er heeft kunnen gebeuren. "Als we nu weten dat het kind 30 is, wat was de kans dat het 10 was?"
De Voorwaartse Rit (Forward Guiding): Vervolgens rijdt de bus terug van begin naar eind. Maar nu rijdt hij niet zomaar; hij wordt "geleid" door de informatie die hij op de terugrit heeft opgedaan. Hij probeert een route te vinden die logisch is voor zowel het begin als het einde.

3. De Magische Bril (Optics)

Hier komt de echte magie van het artikel. De auteurs zeggen: "Deze twee ritten (terug en vooruit) zijn eigenlijk één en hetzelfde object in de wiskunde, genaamd een Optic."

Stel je een Optic voor als een speciale kijker of bril:

Je kijkt erdoorheen in de ene richting (terugrit).
Je kijkt erdoorheen in de andere richting (voorwaartse rit).
Het mooie is: je kunt deze kijkers aan elkaar koppelen.

Als je twee van deze kijkers aan elkaar koppelt (bijvoorbeeld voor twee opeenvolgende jaren), krijg je precies dezelfde resultaten als wanneer je één grote kijker zou maken voor die twee jaren samen.

4. Waarom is dit zo handig? (De Analogie van de Routeplanner)

Stel je voor dat je een routeplanner gebruikt om van Amsterdam naar Tokio te reizen, maar je moet via een tussenstop in Berlijn.

Situatie A (Samenstellen): Je berekent de route Amsterdam -> Berlijn, en daarna Berlijn -> Tokio. Je plakt de twee routes aan elkaar.
Situatie B (Samenvoegen): Je berekent direct de route Amsterdam -> Tokio, alsof Berlijn niet bestaat.

De auteurs bewijzen met hun wiskundige "LEGO-regels" dat Situatie A en Situatie B exact hetzelfde resultaat geven.

Wat betekent dit voor de praktijk?

Gemak: Je hoeft niet het hele algoritme opnieuw te schrijven als je een nieuw stukje toevoegt. Je plakt gewoon een nieuw blokje eraan.
Flexibiliteit: Soms is een route (een wiskundige formule) te ingewikkeld om direct te berekenen. Dan kun je hem opbreken in drie simpele stukjes, die elk makkelijk te berekenen zijn. Dankzij deze "koppelbaarheid" werkt het eindresultaat precies hetzelfde als het moeilijke stuk.
Fouten opvangen: Als je een sensor mist (bijvoorbeeld je hebt geen foto van je kind op zijn 15e), kun je gewoon de twee stukken eromheen aan elkaar plakken. Het algoritme "weet" dat het klopt.

5. De "Lax Monoidal" (De Regel met de Uitzondering)

De auteurs zeggen dat dit systeem bijna perfect werkt, maar er is één kleine nuance.

Als je twee onafhankelijke dingen tegelijk doet (bijvoorbeeld het weer in Nederland en het weer in Brazilië), kun je ze perfect naast elkaar zetten.
Maar als die twee dingen elkaar beïnvloeden (verwarring), moet je een beetje extra "gewicht" (een correctiefactor) toevoegen.
De goede nieuws: Voor de meeste praktische toepassingen (zoals het simuleren van data) maakt die kleine correctie op het eind niets uit. Het resultaat is nog steeds goed genoeg.

Conclusie in één zin

Deze paper laat zien dat complexe wiskundige algoritmen voor het voorspellen van onbekende gebeurtenissen eigenlijk uit bouwstenen bestaan die je op elke manier kunt samenvoegen, net als LEGO, waardoor het bouwen van nieuwe, slimme computersystemen veel makkelijker en flexibeler wordt.

Kortom: Ze hebben de "bouwhandleiding" voor slimme algoritmes herschreven, zodat ingenieurs en wetenschappers makkelijker nieuwe, krachtige systemen kunnen bouwen zonder in de war te raken door de details.

Titel: Compositionality in algoritmen voor smoothing

Auteurs: Moritz Schauer, Frank van der Meulen, Andi Q. Wang
Publicatie: Compositionality, Volume 8, Issue 3 (2026)

1. Probleemstelling

In moderne statistiek en machine learning worden modellen voor Bayesiaanse inferentie op deels waargenomen systemen (zoals Hidden Markov Models of State Space Models) steeds complexer. Een centrale uitdaging bij het analyseren en implementeren van deze algoritmen is het begrijpen van hun compositionaliteit: hoe zijn de fundamentele bouwstenen van een algoritme opgebouwd en hoe verhouden deze zich tot elkaar?

Specifiek richt dit artikel zich op het smoothing-probleem: het afleiden van de verdeling van een stochastisch proces op alle niet-waargenomen (interne) knopen, gegeven waarnemingen op de bladknopen van een gerichte boom. Traditionele methoden, zoals de Kalman-filter of Forward-Backward recursies, werken vaak alleen in gesloten vorm voor specifieke gevallen (bijv. lineair-Gaussisch of eindige toestandsruimtes). Het Backward Filtering Forward Guiding (BFFG) algoritme (Mider et al., 2021) biedt een generalisatie voor bredere scenario's, maar de onderliggende structurele eigenschappen en de manier waarop dit algoritme zich gedraagt bij het combineren van processen (compositie) waren tot nu toe niet formeel vastgelegd in een wiskundig raamwerk.

2. Methodologie

De auteurs gebruiken categorietheorie als wiskundig raamwerk om de BFFG-algoritmen te analyseren. De kern van de methode bestaat uit het vertalen van probabilistische concepten naar categorie-theoretische structuren:

Markov-kernen als categorie: De auteurs benutten de categorie Stoch, waar objecten meetbare ruimtes zijn en morfismen Markov-kernen (overgangs-kansen).
Optics voor bidirectionele dataflow: Omdat BFFG een bidirectioneel algoritme is (een terugwaartse "filter"-pass en een voorwaartse "guiding"-pass), gebruiken ze het concept van Optics (of lenzen) uit de categorietheorie. Optics modelleren systemen met een eerste (forward) en tweede (backward) pass, waarbij een interne toestand (message) wordt doorgegeven.
Functoriële mapping: Het doel is om te bewijzen dat het BFFG-algoritme fungeert als een functor die de categorie van Markov-kernen (Stoch of Stoch²) afbeeldt op de categorie van Optics (Optic(Set)).
Monoidaliteit: De auteurs onderzoeken of deze functor ook monoidaal is, wat betekent dat het algoritme parallelle compositie (onafhankelijke processen) behoudt.

3. Belangrijkste Bijdragen

A. Categorie-theoretische Formulering van BFFG

De auteurs definiëren formeel de twee stappen van BFFG als een optic:

Eerste map (Backward Filtering): Een functie $B_{\tilde{\kappa}}$ die een leidende functie (guiding function) $g$ en een kernel $\tilde{\kappa}$ neemt en een nieuwe functie en een "message" teruggeeft. Dit correspondeert met het berekenen van de achterwaartse filter.
Tweede map (Forward Guiding): Een functie $F_{\kappa, \tilde{\kappa}}$ die de output van de eerste pass gebruikt om een nieuwe verdeling te genereren via een h-transformatie. Dit correspondeert met het voorwaartse simuleren.

De combinatie van deze twee maps vormt een optic $O(\kappa, \tilde{\kappa})$ in de categorie Optic(Set).

B. Functoriële Eigenschappen (Theorema 8)

Het artikel bewijst dat BFFG een contravariante functor is:

Behoud van sequentiële compositie: Als men twee Markov-kernen $\kappa_1$ en $\kappa_2$ samenvoegt tot $\kappa_1 \kappa_2$ , is de resulterende optic equivalent aan de compositie van de individuele optics $O(\kappa_2) \circ O(\kappa_1)$ .
Betekenis: Dit betekent dat het algoritme consistent blijft, ongeacht of men het proces als één grote stap of als meerdere kleine stappen modelleert. Het maakt het mogelijk om complexe grafen op te splitsen in kleinere, beheersbare onderdelen zonder de wiskundige integriteit van het smoothing-algoritme te verliezen.

C. Lax Monoidal Eigenschappen (Theorema 11)

Voor het specifieke geval van Backward Filtering Forward Sampling (BFFS), waarbij de benaderingskernen gelijk zijn aan de generatieve kernen ( $\tilde{\kappa} = \kappa$ ), bewijzen de auteurs dat de functor lax monoidaal is.

Dit betekent dat het parallelle combineren van twee onafhankelijke processen (tensor product) via het algoritme equivalent is aan het combineren van de optics van de afzonderlijke processen, mits men rekening houdt met een natuurlijke transformatie die marginaalverdelingen combineert.
Beperking: Voor het algemene BFFG (waar $\tilde{\kappa} \neq \kappa$ ) faalt de strikte lax monoidaliteit. Dit komt door de noodzaak om globale gewichten (importance weights) bij te houden die afhankelijk zijn van de interactie tussen takken. Echter, de auteurs tonen aan dat dit in de praktijk (bijv. bij Sequential Monte Carlo) geen probleem vormt omdat deze constanten in de uiteindelijke schatter wegvallen.

4. Resultaten en Voorbeelden

De theorie wordt geïllustreerd met concrete toepassingen:

Ontbrekende waarnemingen: Als een sensor faalt en een waarneming ontbreekt op een knoop, kunnen de omliggende kernen wiskundig worden samengevoegd tot één kern zonder dat het algoritme moet worden aangepast (gevolg van Theorema 8).
Intractable overgangen: Als een overgangskern $\kappa$ te complex is om direct te berekenen, maar kan worden opgesplitst in tractabele sub-kernen $\kappa_1$ en $\kappa_2$ , kan het algoritme worden toegepast op de sub-stappen. De compositie-eigenschap garandeert dat dit resulteert in dezelfde verdeling als het direct toepassen op $\kappa$ .
SDE-discretisatie: Voor Stochastische Differentiaalvergelijkingen (SDE's) waarover geen gesloten vorm bestaat, kan de tijd worden opgesplitst in kleine stappen (Euler-discretisatie). De compositie-eigenschap zorgt ervoor dat het samenvoegen van deze stappen geldige smoothing-resultaten oplevert.

5. Significantie en Impact

De bijdrage van dit artikel is tweeledig:

Theoretisch: Het biedt een diepgaand inzicht in de structuur van smoothing-algoritmen door ze te herleiden tot fundamentele categorietheoretische principes. Het toont aan dat er een "hoog-orde structuurbehoudende kern" bestaat in deze algoritmen.
Praktisch: Door de compositie-eigenschappen te formaliseren, krijgen ontwikkelaars een wiskundig onderbouwd kader om complexe inferentieproblemen te modulariseren. Het maakt het mogelijk om algoritmen te bouwen uit herbruikbare componenten (optics) en garandeert dat deze correct werken wanneer ze worden samengevoegd, zelfs in complexe scenario's met ontbrekende data of intractabele overgangen.

Samenvattend vertaalt dit werk het BFFG-algoritme van een specifieke numerieke procedure naar een universeel, samenstellend wiskundig object, wat de weg vrijmaakt voor robuustere en schaalbaardere inferentie-algoritmen in de statistiek en machine learning.