📊 statistics

Lattice Random Walk Discretisations of Stochastic Differential Equations

Dit artikel introduceert een rooster-willekeurige wandeling discretisatieschema voor stochastische differentiaalvergelijkingen dat binaire of ternaire incrementen gebruikt om complexe berekeningen te elimineren, wat leidt tot betere compatibiliteit met stochastische rekenarchitecturen, robuustheid tegen kwantisatiefouten en de mogelijkheid om niet-Lipschitz-driften te verwerken, terwijl zwakke convergentie wordt bewezen en voordelen worden aangetoond in experimenten met diffusiemodellen.

Oorspronkelijke auteurs: Samuel Duffield, Maxwell Aifer, Denis Melanson, Zach Belateche, Patrick J. Coles

Gepubliceerd 2026-02-18

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Samuel Duffield, Maxwell Aifer, Denis Melanson, Zach Belateche, Patrick J. Coles

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

Stel je voor dat je probeert het pad van een dronken wandelaar te voorspellen. Deze wandelaar loopt niet alleen in een rechte lijn (dat is de drift, of de bedoeling), maar wordt ook constant door de wind en onvoorspelbare stoten van de grond opzij geduwd (dat is de diffusie of ruis).

In de wiskunde noemen we dit een Stochastische Differentiaalvergelijking (SDE). Computers moeten deze paden simuleren om bijvoorbeeld nieuwe foto's te maken (zoals bij AI), beursprijzen te voorspellen of moleculen te bestuderen.

Het probleem? De huidige manier waarop computers dit doen, is als een zeer precieze, maar zware en dure machine die alles in oneindig veel decimalen berekent. Dat kost veel energie, tijd en is gevoelig voor kleine foutjes.

De auteurs van dit paper (van Normal Computing Corporation) hebben een slimme nieuwe manier bedacht: de Lattice Random Walk (LRW). Laten we dit uitleggen met een paar creatieve analogieën.

1. De oude manier: De "Gouden Liniaal" (Euler-Maruyama)

Stel je voor dat je de wandelaar probeert te volgen met een gouden liniaal die oneindig nauwkeurig is.

Je meet elke seconde hoe ver de wind de wandelaar duwt.
Je berekent de exacte positie tot op de nanometer.
Het probleem: Om dit te doen, moet je complexe wiskunde doen (zoals het trekken van wortels en het genereren van "Gaussische" getallen, die op een computer eigenlijk maar een benadering zijn van echte willekeur). Als je computer een klein beetje fout rekent (door afronding), stapelt die fout zich op. En als de wind plotseling heel sterk wordt (een "niet-Lipschitz" drift), kan de berekening volledig uit de hand lopen en exploderen.

2. De nieuwe manier: Het "Schaakbord" (Lattice Random Walk)

De auteurs zeggen: "Waarom proberen we die nanometers te meten? Laten we de wandelaar simpelweg op een groot schaakbord zetten."

In plaats van oneindig veel decimalen, laten we de wandelaar alleen op de snijpunten van het rooster (de lattice) staan.

De stap: Bij elke stap kan de wandelaar alleen links, rechts of stil blijven staan.
De magie: In plaats van te rekenen waar hij precies moet zijn, berekent de computer alleen de kans dat hij links, rechts of stil blijft.
De uitvoering: De computer hoeft dan alleen maar een muntje op te gooien (of een dobbelsteen met drie kanten) om te beslissen welke kant hij op gaat.

Waarom is dit zo geweldig? (De 4 grote voordelen)

A. Geen zware "Gaussische" berekeningen meer

Bij de oude manier moet de computer een complexe formule gebruiken om een willekeurig getal te maken dat lijkt op een normale verdeling (een klokkromme). Dat is zwaar werk.

De analogie: Het is alsof je voor elke stap een heel restaurant moet bellen om een perfecte maaltijd te bestellen.
Met LRW: Je gooit gewoon een muntje op. Links of rechts. Dat is veel sneller en simpeler voor een computerchip.

B. Robuust tegen "ruis" (Kwantiseringsfouten)

Computers werken met beperkte precisie (bijvoorbeeld 16 bits in plaats van 32 bits).

Oude manier: Als je een kleine fout maakt in de berekening van de wind, wordt die fout groter en groter bij elke stap. De wandelaar verdwaalt.
Nieuwe manier: Omdat de wandelaar vastzit aan het rooster (hij kan niet halverwege een vakje staan), maakt het niet uit als de kansberekening een klein beetje fout is. De uitkomst is nog steeds "links" of "rechts". Het rooster "veegt" de kleine fouten weg. Het is alsof je op een trampoline springt: als je een beetje scheef landt, veer je toch terug naar het midden van het vakje.

C. Het kan "explosieve" winden aan

Soms wordt de wind zo sterk dat de wandelaar oneindig ver weg zou kunnen vliegen.

Oude manier: De berekening wordt zo groot dat de computer vastloopt (overloop).
Nieuwe manier: De wandelaar kan per stap maar één vakje op of neer. Het is fysiek onmogelijk voor hem om te "exploderen", ongeacht hoe hard de wind waait. Hij blijft veilig op het rooster.

D. De droom van "Stochastisch Rekenen"

Dit is misschien wel het coolste deel. Er bestaat een type computerchips die niet rekenen met getallen, maar met stroompjes van bits (0 en 1).

Het probleem: Normale AI-modellen moeten aan het einde van de berekening die bits weer omzetten naar een groot getal. Dat kost tijd en vernietigt het voordeel.
De oplossing: Omdat onze nieuwe methode (LRW) al werkt met bits (links/rechts/stil), hoeft er niets meer omgezet te worden! De computer kan de hele reis van de wandelaar simuleren met alleen maar schakelaars die aan en uit gaan. Dit kan leiden tot enorme snelheidswinsten en veel minder energieverbruik.

Wat hebben ze bewezen?

De auteurs hebben wiskundig bewezen dat deze "schaakbord-methode" net zo goed werkt als de oude, zware methode als je de stappen klein genoeg maakt. Ze hebben het ook getest:

Simpele tests: Het werkt beter dan de oude methode bij lage precisie.
Moeilijke tests: Het werkt stabiel bij modellen die normaal gesproken zouden "exploderen".
AI-Tests: Ze hebben het gebruikt bij Stable Diffusion 3.5 (een van de beste AI-foto-generators ter wereld). Het bleek dat de AI nog steeds prachtige foto's kon maken, zelfs met deze simpele "rooster-methode".

Conclusie

Dit paper introduceert een manier om complexe, willekeurige bewegingen te simuleren door ze terug te brengen tot simpele "ja/nee" of "links/rechts" beslissingen op een rooster.

Het is alsof je een dure, precieze raceauto (de oude methode) vervangt door een robuuste, snelle mountainbike (de nieuwe methode). De mountainbike is makkelijker te bouwen, minder gevoelig voor steentjes op de weg, en kan zelfs op paden rijden waar de raceauto vastloopt. En het beste van alles: hij past perfect op een nieuw soort fietspad dat speciaal voor mountainbikes is ontworpen (stochastische hardware).

Titel: Rooster Random Walk Discretisaties van Stochastische Differentiaalvergelijkingen

Auteurs: Samuel Duffield et al. (Normal Computing Corporation)

1. Het Probleem

Stochastische differentiaalvergelijkingen (SDE's) zijn fundamenteel voor veel gebieden, waaronder natuurkunde, financiën, biologie en machine learning (met name voor diffusion modellen in beeldgeneratie). Het simuleren van SDE's op digitale computers vormt echter aanzienlijke uitdagingen:

Continu vs. Discreet: SDE's zijn continu-tijd objecten met willekeurige ruis, terwijl digitale computers discrete operaties uitvoeren.
Beperkingen van Euler-Maruyama: De meest gebruikte numerieke methode, Euler-Maruyama (EM), heeft ernstige tekortkomingen:
- Aanname van oneindige precisie: Het is gevoelig voor kwantisatiefouten in hardware-implementaties.
- Gaussische sampling: Het vereist het genereren van Gaussische verdelingen, wat niet-natuurlijk is voor bit-gebaseerde hardware en complexe transcendentale functies vereist.
- Instabiliteit: Het faalt vaak bij niet-Lipschitz-driftfuncties (waar de drift sneller dan lineair groeit), wat leidt tot explosief gedrag.
- Hardware-inefficiëntie: Het is niet optimaal voor moderne parallelle hardware en biedt weinig voordelen voor specifieke "stochastic computing" architecturen.

2. Methodologie: Lattice Random Walk (LRW)

De auteurs introduceren een nieuw discretisatieschema genaamd Lattice Random Walk (LRW). In plaats van continue waarden te berekenen, discretiseert LRW de SDE door op elke stap een binair of ternair increment te samplingen.

Het Kernconcept:
Voor een SDE van de vorm $dx = f(x, t)dt + \sigma(x, t)dw$ , wordt de update regel als volgt gedefinieerd:
$x_{t+\delta t} = x_t + \Delta(x_t, t)$
Waarbij $\Delta$ een ternaire verdeling is met mogelijke waarden $\{-\delta x, 0, +\delta x\}$ . De kansen voor deze waarden ( $p_-, p_0, p_+$ ) worden zo gekozen dat de eerste en tweede momenten van het increment overeenkomen met de drift en diffusie van de onderliggende SDE:

$E[\Delta] = \delta t \cdot f(x, t)$
$E[\Delta^2] = \delta t \cdot \sigma(x, t)^2$

Belangrijke parameters:

$\delta t$ : Tijdstap.
$\delta x$ : Ruimtestap (ruimtelijke stapgrootte).
De auteurs tonen aan dat een "vuistregel" voor $\delta x = \sqrt{\delta t \sigma_{max}}$ leidt tot een stabiele binair/ternair proces dat voldoet aan de convergentie-eisen.

Aannames:
De methode gaat momenteel uit van een diagonale diffusiematrix $\sigma(x, t)$ . Voor dichte matrices kan een Lamperti-transformatie worden toegepast om dit te omzeilen.

3. Belangrijkste Bijdragen

Weak Convergence Bewijs: De auteurs bewijzen wiskundig dat het LRW-schema convergeert met weak order 1 (dezelfde convergentiesnelheid als Euler-Maruyama) naar de ware SDE-oplossing wanneer $\delta t \to 0$ , mits $\delta x = \Theta(\sqrt{\delta t})$ .
Eliminatie van Gaussische Sampling: LRW vereist geen Gaussische verdelingen. Het samplingen van binaire/ternaire waarden is een veel eenvoudigere operatie die direct aansluit bij digitale hardware.
Robuustheid tegen Kwantiseringsfouten: Omdat de output op een rooster (lattice) ligt, worden fouten in de berekening van drift en diffusie "geabsorbeerd" in de kansen van de verdeling. Kleine perturbaties leiden vaak tot hetzelfde discrete resultaat, wat LRW zeer robuust maakt voor hardware met beperkte precisie (bijv. 8-bit of 16-bit).
Stabiliteit bij Niet-Lipschitz Drift: In tegenstelling tot Euler-Maruyama, dat kan exploderen bij grote driftwaarden, beperkt de discrete aard van LRW elke stap tot $\pm \delta x$ of $0$. Dit voorkomt explosief gedrag zelfs bij niet-globaal Lipschitz-driftfuncties.
Compatibiliteit met Stochastic Computing: LRW is ideaal voor "stochastic computing" architecturen (waarbij getallen worden gerepresenteerd als bitstromen). Het elimineert de noodzaak om bitstromen aan het einde van de simulatie weer terug te converteren naar hoge precisie reële getallen, wat een grote bottleneck in traditionele stochastic computing is.

4. Experimentele Resultaten

De auteurs testen LRW op drie verschillende scenario's:

Ornstein-Uhlenbeck (OU) Proces:
- LRW toont superieure robuustheid tegen kwantisatiefouten (bij 16-bit en 8-bit precisie) vergeleken met Euler-Maruyama.
- Bij lage precisie en grote stapgroottes faalt Euler-Maruyama, terwijl LRW accuraat blijft.
Poisson Random Effects Model (Niet-Lipschitz):
- Bij een driftfunctie die niet globaal Lipschitz is, explodeert de fout van Euler-Maruyama bij grotere stapgroottes.
- LRW blijft stabiel en accuraat over een breed scala aan stapgroottes.
Stable Diffusion 3.5 (Beeldgeneratie):
- LRW wordt toegepast op een state-of-the-art diffusion model (8+ miljard parameters).
- Bij 50 stappen zijn de gegenereerde beelden kwalitatief gelijk aan die van Euler-Maruyama.
- Bij 25 stappen is LRW nog steeds van hoge kwaliteit, hoewel er iets meer "korreligheid" (ruis) zichtbaar is, wat wordt toegeschreven aan het kleinere tweede moment van de LRW-update vergeleken met EM.
- Dit bewijst dat LRW schaalbaar is naar complexe, moderne machine learning pipelines.

5. Betekenis en Toekomstperspectief

Hardware Beschleuniging: De grootste potentie van LRW ligt in de implementatie op gespecialiseerde hardware voor stochastic computing. Omdat de berekeningen worden gereduceerd tot het samplingen van binaire/ternaire waarden, kunnen er enorme snelheids- en energiebesparingen worden behaald ten opzichte van traditionele floating-point GPU's.
Toepassing in AI: De methode opent de deur voor het efficiënter trainen en infereren van diffusion modellen en Bayesiaanse inferentie, met name in scenario's waar kwantisatie en energie-efficiëntie cruciaal zijn.
Beperkingen: De huidige implementatie vereist een diagonale diffusiematrix. Uitbreiding naar dichte matrices en het bereiken van weak order 2 convergentie worden aangewezen als richtingen voor toekomstig werk.

Conclusie:
Dit paper introduceert een fundamenteel nieuw paradigma voor het oplossen van SDE's. Door over te stappen van continue floating-point berekeningen naar discrete rooster-walks, lossen de auteurs de problemen van kwantisatie, instabiliteit bij niet-Lipschitz functies en inefficiëntie op stochastic computing hardware op, zonder in te leveren op de convergentie-eigenschappen die nodig zijn voor moderne machine learning toepassingen.