Differentiable Particle Filtering using Optimal Placement Resampling

Deze paper introduceert een differentieerbare resampling-methode voor partikelfilters, gebaseerd op deterministische steekproeven uit een empirische cumulatieve verdelingsfunctie, om gradiëntgebaseerde parameterinference en voorstel-leren mogelijk te maken in niet-lineaire en niet-Gaussische toestandsruimtemodellen.

De kern

Stel je voor dat je probeert het weer te voorspellen, maar je hebt geen perfecte meetinstrumenten. Je hebt alleen een groepje "waarzeggers" (we noemen ze in de paper deeltjes of particles). Elke waarzegger heeft een eigen idee over hoe het weer morgen wordt, en ze hebben allemaal een beetje meer of minder vertrouwen (een gewicht) op basis van hoe goed hun eerdere voorspellingen klopten.

Dit is de basis van een Deeltjesfilter: een slimme manier om onzekerheid te managen door te gokken met een heleboel mogelijke scenario's.

Hier is wat dit paper doet, vertaald naar alledaags taal:

1. Het Probleem: De "Gokkast" die niet kan leren

In de traditionele methode, als je ziet dat bepaalde waarzeggers veel beter hebben gepresteerd, doe je iets heel drastisch: je laat de slechte waarzeggers verdwijnen en je maakt kopieën van de beste waarzeggers. Dit heet resampling.

Stel je voor dat je een gokkast hebt. Als je wint, krijg je een bonus-veer. Maar hier is het probleem: deze vermenigvuldiging is een ruwe, haperende actie.

• Als je de instellingen van je computer (de parameters) een heel klein beetje verandert, kan het zijn dat plotseling een heel andere groep waarzeggers wordt gekopieerd.
• Voor een computer die probeert te leren (zoals een AI), is dit een nachtmerrie. Het kan niet begrijpen waarom het beter ging. Het is alsof je probeert een auto te sturen terwijl het stuur soms vastzit en soms plotseling naar links springt. Je kunt niet zachtjes sturen; je kunt alleen hopen dat je toevallig goed zit.

Dit maakt het onmogelijk om de computer slim te maken door hem te laten "leren" uit fouten, omdat de computer geen gradiënt (een richting om beter te worden) kan berekenen.

2. De Oplossing: De "Perfecte Rangschikking"

De auteurs van dit paper zeggen: "Laten we stoppen met het willekeurig kopiëren van mensen. Laten we in plaats daarvan iedereen verplaatsen naar de perfecte plek."

Ze introduceren een nieuwe methode genaamd Optimal Placement Resampling.

• De Analogie: Stel je hebt een rij mensen die staan op een heuvel. Sommigen staan op de top (hoog gewicht), anderen in de vallei (laag gewicht).
• De oude methode: Je neemt de mensen in de vallei en gooit ze weg. Je pakt de mensen op de top en maakt er twintig kopieën van. Het resultaat is een hoop mensen op één punt, en de rest is leeg.
• De nieuwe methode (OPR): Je zegt tegen iedereen: "Blijf staan, maar verplaats je een beetje." Je zorgt ervoor dat de mensen die in de vallei stonden, nu netjes verspreid staan over de helling, precies waar de kans het grootst is. Niemand wordt weggegooid, niemand wordt gekopieerd. Iedereen krijgt een nieuwe, perfecte positie.

Het belangrijkste is dat dit verplaatsen glad gebeurt. Als je de instellingen van je computer een heel klein beetje verandert, bewegen de mensen ook maar een heel klein beetje. Geen sprongen, geen haperingen.

3. Waarom is dit geweldig?

Omdat de beweging nu "glad" is, kan de computer leren.

• De computer kan nu precies zien: "Als ik deze knop een beetje draai, bewegen de waarzeggers naar een betere plek en wordt mijn voorspelling beter."
• Hierdoor kan de computer zichzelf verbeteren in taken waar dat voorheen onmogelijk was, zoals het leren van complexe modellen voor beurskoersen of robotnavigatie.

4. Wat hebben ze getest?

Ze hebben hun nieuwe methode getest op drie dingen:

1. Een simpele lineaire wereld: Hier werkte het net zo goed als de oude methode, maar dan zonder de haperingen.
2. Het leren van de "gokstrategie": Ze lieten de computer leren hoe hij de waarzeggers het beste moet verplaatsen. De oude methode faalde hier (de computer leerde niets), maar de nieuwe methode leerde snel en nauwkeurig.
3. Beurskoersen (Stochastische Volatiliteit): Ze gebruikten echte data van wisselkoersen (EUR/HUF). De nieuwe methode gaf een veel betere voorspelling dan de oude methode.

Samenvatting in één zin

De auteurs hebben een manier bedacht om de "ruwe" en onleerbare stap in het voorspellen van de toekomst (het kopiëren van de beste scenario's) te vervangen door een gladde, continue verplaatsing, zodat computers eindelijk kunnen leren hoe ze de beste voorspellingen kunnen doen.

De grote beperking: Op dit moment werkt deze "perfecte rangschikking" alleen goed in één dimensie (zoals een lijn). Als je het in 3D moet doen (zoals in een ruimte), wordt het een stuk moeilijker, maar dat is de volgende stap voor de onderzoekers.

Technische samenvatting

Probleemstelling

Deelnamefilters (Particle Filters, PFs) zijn een standaardmethode voor inferentie in niet-lineaire en niet-Gaussische toestandsruimtemodellen (SSMs). Ze worden gebruikt voor het schatten van latente toestanden of voor het leren van modelparameters via maximum likelihood schatting (MLE).

Het centrale probleem dat in dit artikel wordt aangepakt, is de niet-differentieerbaarheid van traditionele resampling-methoden (zoals multinomiale resampling).

• Bij het trainen van neurale netwerken of het optimaliseren van modelparameters met gradiëntgebaseerde methoden (zoals backpropagation), is het nodig dat de volledige berekeningsketen differentieerbaar is.
• Traditionele resampling is stochastisch en discontinu: kleine veranderingen in modelparameters kunnen leiden tot abrupte veranderingen in welke deeltjes worden geresampled.
• Dit veroorzaakt een hoge variatie in de gradiëntschattingswaarde en maakt backpropagation door de tijd (BPTT) onmogelijk, wat het leren van complexe proposal-distributies of modelparameters blokkeert.

Methodologie: Optimal Placement Resampling (OPR)

De auteurs stellen een nieuwe, deterministische resampling-methode voor genaamd Optimal Placement Resampling (OPR). In plaats van deeltjes stochastisch te herhalen op basis van hun gewichten, worden de deeltjes deterministisch verplaatst naar optimale posities.

De kern van de methode bestaat uit de volgende stappen:

1. Empirische CDF Constructie: In plaats van een stapfunctie (zoals bij traditionele empirische CDF's), wordt de kansdichtheidsfunctie (PDF) benaderd door een gewogen som van Heaviside-functies. Dit resulteert in een continue en differentieerbare cumulatieve verdelingsfunctie (CDF) die lineaire en logaritmische termen bevat.
2. Optimale Posities: De auteurs baseren zich op het werk van Schrempf et al., waarbij de positie van de deeltjes ($x_i$) wordt gekozen om de integraal van het kwadratische verschil tussen de ware CDF en de benaderde CDF te minimaliseren. De optimale positie wordt gegeven door de relatie:
   $$F(x_i) = \frac{2i - 1}{2N}$$
   waarbij $N$ het aantal deeltjes is.
3. Deterministische Verplaatsing: Om de nieuwe posities te vinden, wordt de inverse CDF ($F^{-1}$) gebruikt. Omdat de auteurs een specifieke, makkelijk inverteerbare vorm voor de CDF hebben gekozen (met exponentiële randen en lineaire segmenten), kan de inverse analytisch worden berekend.
4. Resultaat: De gewogen deeltjes worden vervangen door een set van ongewogen deeltjes die zich op de optimale posities bevinden. Dit proces is volledig differentieerbaar, waardoor gradiënten door de resampling-stap kunnen worden teruggepropageerd.

Belangrijkste Bijdragen

• Differentieerbare Resampling: De introductie van OPR als een oplossing voor het differentieerbaarheidsprobleem in PFs, waardoor gradiëntgebaseerd leren van parameters en proposal-distributies mogelijk wordt.
• Deterministische Benadering: Het gebruik van deterministische steekproeven uit een handgemaakte empirische CDF, in tegenstelling tot eerdere werken die stochastische benaderingen of bias in de gradiënt gebruikten.
• Behoud van Diversiteit: De methode elimineert duplicaten (een veelvoorkomend probleem bij resampling) en behoudt de diversiteit van de deeltjesset, terwijl deeltjes toch geconcentreerd blijven in gebieden met hoge waarschijnlijkheid.
• Efficiëntie: Het algoritme heeft een tijdcomplexiteit van $O(N)$, waarbij het sorteren van deeltjes de meest tijdrovende stap is.

Resultaten

De auteurs evalueren hun methode op drie scenario's en vergelijken deze met traditionele PFs met multinomiale resampling (PF-MR):

1. Lineair Gaussisch SSM (LGSSM):

   • Bij het schatten van parameters in een eenvoudig lineair model presteerde OPR vergelijkbaar met PF-MR. In dit geval was de niet-differentieerbaarheid van PF-MR geen groot probleem, maar OPR leverde een nauwkeurigere schatting van de log-likelihood.

2. Leren van Proposal-distributies:

   • Bij het leren van een tijdsvariërende proposal-distributie (waarbij backpropagation door de tijd essentieel is) presteerde PF-MR slecht vanwege de hoge variatie en het ontbreken van gradiënten door de resampling-stap.
   • PF-OPR slaagde erin om de proposal-parameters effectief te leren, wat resulteerde in een hogere Evidence Lower Bound (ELBO). De reductie in ELBO bij PF-MR bevestigt dat de niet-differentieerbaarheid hier een bottleneck is.

3. Stochastische Volatiiliteitsmodel (Financiële Data):

   • Toegepast op een complex niet-lineair model met dagelijkse wisselkoersen (EUR/HUF).
   • PF-OPR bereikte een ELBO van -634,9, terwijl PF-MR uitkwam op -640,0. Een hogere ELBO (dichter bij 0) duidt op een betere schatting van de marginale data-likelihood.
   • Dit bewijst dat OPR een strakkere ondergrens biedt en beter presteert bij parameterinferentie in complexe, real-world scenario's.

Significantie en Toekomstperspectief

Deze studie is significant omdat het een praktische en effectieve oplossing biedt voor een fundamenteel probleem in het combineren van Bayesiaanse filtering en diep leren. Het maakt het mogelijk om PFs als "neurale netwerken" te behandelen waarbij alle componenten, inclusief resampling, kunnen worden geoptimaliseerd via gradiëntafstijging.

Beperkingen en Toekomstig Werk:

• De huidige implementatie werkt alleen in één dimensie. De methode is afhankelijk van de unidimensionale eigenschap van de CDF (waarbij $P(X \le x)$ uniek is).
• In hogere dimensies is de CDF niet uniek gedefinieerd. De auteurs wijzen erop dat toekomstig werk gericht moet zijn op het ontwikkelen van vergelijkbare strategieën voor multidimensionale ruimten, bijvoorbeeld door alternatieve CDF-benaderingen of andere plaatsingsstrategieën.

Samenvattend biedt dit artikel een robuuste methode om de "niet-differentieerbare muur" in Particle Filters te doorbreken, wat leidt tot betere prestaties bij het leren van complexe dynamische systemen.