Probabilistiska siffror

Probabilistisk numerik är ett vetenskapligt område i skärningspunkten mellan statistik , maskininlärning och tillämpad matematik , där uppgifter inom numerisk analys inklusive att hitta numeriska lösningar för integration , linjär algebra , optimering och differentialekvationer ses som problem med statistisk, probabilistisk eller Bayesiansk slutledning .

Introduktion

En numerisk metod är en algoritm som approximerar lösningen på ett matematiskt problem (exempel nedan inkluderar lösningen på ett linjärt ekvationssystem , värdet av en integral , lösningen av en differentialekvation , minimum av en multivariatfunktion). I en probabilistisk numerisk algoritm betraktas denna approximationsprocess som ett problem med uppskattning , slutledning eller inlärning och realiseras inom ramen för probabilistisk slutledning (ofta, men inte alltid, Bayesiansk slutledning ).

Formellt innebär detta att man gjuter uppsättningen av beräkningsproblemet i termer av en tidigare fördelning , formulerar förhållandet mellan tal som beräknats av datorn (t.ex. matris-vektormultiplikationer i linjär algebra, gradienter i optimering, värden för integranden eller vektorfältsdefinitionen en differentialekvation) och kvantiteten i fråga (lösningen av det linjära problemet, minimum, integralen, lösningskurvan) i en sannolikhetsfunktion , och returnerar en bakre fördelning som utdata. I de flesta fall tar numeriska algoritmer även interna adaptiva beslut om vilka tal som ska beräknas, vilket utgör ett aktivt inlärningsproblem .

Många av de mest populära klassiska numeriska algoritmerna kan omtolkas i det probabilistiska ramverket. Detta inkluderar metoden för konjugerade gradienter , Nordsieck-metoder , Gaussiska kvadraturregler och kvasi-Newton-metoder . I alla dessa fall är den klassiska metoden baserad på en regulariserad minsta kvadraters uppskattning som kan associeras med det bakre medelvärdet som härrör från en Gaussisk prioritet och sannolikhet. I sådana fall associeras variansen av Gauss-posterioren sedan med en värsta uppskattning för kvadratfelet.

Probabilistiska numeriska metoder lovar flera konceptuella fördelar jämfört med klassiska, punktskattningsbaserade approximationstekniker:

De returnerar strukturerade feluppskattningar (särskilt förmågan att returnera posteriora ledprover, dvs. flera realistiska hypoteser för den verkligt okända lösningen av problemet)
Hierarkisk Bayesiansk slutledning kan användas för att ställa in och kontrollera interna hyperparametrar i sådana metoder på ett generiskt sätt, snarare än att behöva återuppfinna nya metoder för varje parameter
Eftersom de använder och tillåter en explicit sannolikhet som beskriver förhållandet mellan beräknade tal och målkvantitet, kan probabilistiska numeriska metoder använda resultaten av till och med mycket oprecisa, partiska och stokastiska beräkningar. Omvänt kan probabilistiska numeriska metoder också ge en sannolikhet i beräkningar som ofta anses vara " sannolikhetsfria" någon annanstans
Eftersom alla probabilistiska numeriska metoder använder i huvudsak samma datatyp – sannolikhetsmått – för att kvantifiera osäkerhet över både indata och utdata kan de kedjas samman för att sprida osäkerhet över storskaliga, sammansatta beräkningar
Källor från flera informationskällor (t.ex. algebraisk, mekanistisk kunskap om formen av en differentialekvation och observationer av systemets bana som samlas in i den fysiska världen) kan kombineras naturligt och inuti den inre slingan av algoritmen, vilket tar bort annars nödvändiga kapslade loopar i beräkning, t.ex. i omvända problem .

Dessa fördelar är i huvudsak motsvarigheten till liknande funktionella fördelar som Bayesianska metoder åtnjuter jämfört med punktuppskattningar i maskininlärning, tillämpade eller överförda till beräkningsdomänen.

Numeriska uppgifter

Integration

Bayesisk kvadratur med en Gauss-process betingad av

n=0,3,\ {\text{and}}\ 8

av integranden (visas i svart). Skuggade områden i den vänstra kolumnen illustrerar de marginella standardavvikelserna. Den högra figuren visar den föregående (

n=0

) och posterior (

n=3,8

) Gauss-fördelningen över värdet på integralen, såväl som den sanna lösningen .

Probabilistiska numeriska metoder har utvecklats för problemet med numerisk integration , med den mest populära metoden kallad Bayesian quadrature .

I numerisk integration, funktionsutvärderingar $f(x_{1}),\ldots ,f(x_{n})$ vid ett antal punkter $x_{1},\ldots ,x_{n}$ används för att uppskatta integralen $\textstyle \int f(x)\nu (dx )$ av en funktion $f$ mot något mått $\nu$ . Bayesisk kvadratur består av att specificera en tidigare fördelning över $f$ och konditionera denna prior på $f(x_{1}),\ldots ,f(x_ {n})$ för att erhålla en posterior fördelning över $f$ , beräkna sedan den implicita bakre fördelningen på $\textstyle \int f(x)\nu (dx )$ . Det vanligaste valet av prior är en Gauss-process eftersom detta tillåter oss att erhålla en sluten form posterior distribution på integralen som är en univariat Gauss-fördelning. Bayesisk kvadratur är särskilt användbar när funktionen $f$ är dyr att utvärdera och dimensionen på data är liten till måttlig.

Optimering

Bayesiansk optimering av en funktion (svart) med Gaussiska processer (lila). Tre inhämtningsfunktioner (blå) visas längst ner.

Probabilistiska tillvägagångssätt har också studerats för matematisk optimering , som består av att hitta minimum eller maximum för någon objektiv funktion $\displaystyle f}$ givna (möjligen bullriga eller indirekta) utvärderingar av den funktionen vid en uppsättning punkter.

Den kanske mest anmärkningsvärda ansträngningen i denna riktning är Bayesiansk optimering , ett allmänt tillvägagångssätt för optimering grundat på Bayesiansk slutledning. Bayesianska optimeringsalgoritmer fungerar genom att upprätthålla en probabilistisk övertygelse om $f$ under hela optimeringsproceduren; detta tar ofta formen av en Gauss-process som tidigare betingats av observationer. Denna övertygelse styr sedan algoritmen för att erhålla observationer som sannolikt kommer att främja optimeringsprocessen. Bayesianska optimeringspolicyer realiseras vanligtvis genom att transformera den objektiva funktionen posterior till en billig, differentierbar förvärvsfunktion som är maximerad för att välja varje successiv observationsplats. Ett framträdande tillvägagångssätt är att modellera optimering via Bayesiansk sekventiell experimentell design , i syfte att erhålla en sekvens av observationer som ger de mest optimeringsframsteg som utvärderas av en lämplig hjälpfunktion . En välkommen bieffekt av detta tillvägagångssätt är att osäkerhet i den objektiva funktionen, mätt med den underliggande sannolikhetsuppfattningen, kan vägleda en optimeringspolicy för att ta itu med den klassiska avvägningen mellan utforskning och exploatering .

Lokal optimering

Probabilistiska numeriska metoder har utvecklats i samband med stokastisk optimering för djupinlärning , särskilt för att ta itu med huvudfrågor som inlärningshastighetsinställning och linjesökningar , val av batchstorlek, tidig stopp , beskärning och första och andra ordningens sökriktningar .

I den här inställningen är optimeringsmålet ofta en empirisk risk av formen ${\displaystyle \textstyle L(\theta )= {\frac {1}{N}}\sum _{n=1}^{N}\ell (y_{n},f_{\theta }(x_{n}))} definierad av en$ datauppsättning $\textstyle {\mathcal {D}}=\{(x_{n},y_{n})\}_{n=1}^{N}$ , och en förlust $\ell (y,f_{\theta }(x))$ som kvantifierar hur väl en prediktiv modell $f_{ \theta }(x)$ parametriserad av $\theta$ utför på att förutsäga målet $y$ från dess motsvarande ingång $x$ . Epistemisk osäkerhet uppstår när datauppsättningsstorleken $N$ är stor och inte kan bearbetas på en gång, vilket innebär att lokala kvantiteter (givna några $\theta$ ) såsom förlustfunktionen $L( \theta )$ själv eller dess gradient $\nabla L(\theta )$ kan inte beräknas inom rimlig tid. Därför används generellt mini-batching för att konstruera estimatorer av dessa kvantiteter på en slumpmässig delmängd av data. Probabilistiska numeriska metoder modellerar denna osäkerhet explicit och möjliggör automatiserade beslut och parameterinställning.

Linjär algebra

Probabilistiska numeriska metoder för linjär algebra har främst fokuserat på att lösa system av linjära ekvationer av formen $Ax=b$ och beräkning av determinanter $|A|$ .

Illustration av en matrisbaserad probabilistisk linjär lösare.

En stor klass av metoder är iterativ till sin natur och samlar in information om det linjära systemet som ska lösas via upprepad matris-vektor multiplikation $v\mapsto Av$ med systemmatrisen $A$ med olika vektorer $v$ . Sådana metoder kan grovt delas upp i ett lösnings- och ett matrisbaserat perspektiv, beroende på om tro uttrycks över lösningen $x$ i det linjära systemet eller (pseudo-)inversen av matrisen $H=A^{\dolk }$ . Trosuppdateringen använder att det härledda objektet är länkat till matrismultiplikationer $y=Av$ eller $z=A^{\intercal }v$ via $b^{\intercal }z=x^{\intercal }v$ och $v=A^{-1}y$ . Metoder antar vanligtvis en Gaussisk fördelning, på grund av dess slutenhet under linjära observationer av problemet. Även om de är begreppsmässigt olika, är dessa två vyer beräkningsmässigt ekvivalenta och i sig kopplade via den högra sidan genom $x=A^{-1}b$ .

Probabilistiska numeriska linjära algebrarutiner har framgångsrikt tillämpats för att skala Gaussiska processer till stora datamängder. I synnerhet möjliggör de exakt fortplantning av approximationsfelet till en kombinerad Gauss-process posterior, som kvantifierar den osäkerhet som uppstår från både det ändliga antalet observerade data och den ändliga mängden beräkning som förbrukats.

Vanliga differentialekvationer

Prover från den första komponenten i den numeriska lösningen av Lorenz-systemet erhållna med en probabilistisk numerisk integrator.

Probabilistiska numeriska metoder för vanliga differentialekvationer ${\displaystyle {\dot {y}}(t)=f(t,y(t))} har$ utvecklats för initiala och gränsvärdesproblem. Många olika probabilistiska numeriska metoder utformade för vanliga differentialekvationer har föreslagits, och dessa kan i stort sett grupperas i följande två kategorier:

Randomiseringsbaserade metoder definieras genom slumpmässiga störningar av standarddeterministiska numeriska metoder för vanliga differentialekvationer. Till exempel har detta uppnåtts genom att lägga till gaussiska störningar på lösningen av enstegsintegratorer eller genom att slumpmässigt störa deras tidssteg. Detta definierar ett sannolikhetsmått på lösningen av differentialekvationen som kan samplas.
Gaussiska processregressionsmetoder bygger på att ställa problemet med att lösa den aktuella differentialekvationen som ett Gaussisk processregressionsproblem, och tolka utvärderingar av högersidan som data om derivatan. Dessa tekniker liknar Bayesian kubaturen, men använder olika och ofta icke-linjära observationsmodeller. I sin linda baserades denna klass av metoder på naiv Gaussisk processregression . Detta förbättrades senare (när det gäller effektiv beräkning) till förmån för Gauss–Markov-priorer modellerade av den ${\displaystyle \mathrm { d} x(t)=Ax(t)\,\mathrm {d} t+B\,\mathrm {d} v(t)} , där x ( t ) {\displaystyle$ differentialekvationen x $är$ ett $\nu$ -dimensionell vektor som modellerar de första $\nu$ derivatorna av $y(t)$ , och där $v(t)$ är en $\nu$ -dimensionell Brownsk rörelse . Inferens kan således implementeras effektivt med Kalman-filtreringsbaserade metoder.

Gränsen mellan dessa två kategorier är inte skarp, verkligen en Gaussisk processregressionsmetod baserad på randomiserade data utvecklades också. Dessa metoder har tillämpats på problem i beräkningsmässig Riemannsk geometri, omvända problem, latenta kraftmodeller och på differentialekvationer med en geometrisk struktur som symplecticitet.

Partiella differentialekvationer

Ett antal probabilistiska numeriska metoder har också föreslagits för partiella differentialekvationer . Liksom med vanliga differentialekvationer kan tillvägagångssätten i stort sett delas in i de som är baserade på randomisering, i allmänhet av något underliggande finita elementnät och de som är baserade på Gaussisk processregression.

Lära sig lösa en partiell differentialekvation. En problemspecifik Gauss-process före

u

är betingad av delvis känd fysik, givet av osäkra randvillkor (BC) och en linjär PDE, såväl som på bullriga fysiska mätningar från experiment. Gränsvillkoren och den högra sidan av PDE är inte kända men härleds från en liten uppsättning bruskorrupta mätningar. Plotterna ställer tron

u\mid \cdots

samman med den sanna lösningen

u^{\star }

för det latenta gränsvärdesproblemet.

Probabilistiska numeriska PDE-lösare baserade på Gaussisk processregression återvinner klassiska metoder på linjära PDE:er för vissa tidigare, i synnerhet metoder för medelvägda residualer, som inkluderar Galerkin-metoder , finita elementmetoder , såväl som spektrala metoder .

Historia och relaterade områden

Samspelet mellan numerisk analys och sannolikhet berörs av ett antal andra områden inom matematiken, inklusive medelvärdesanalys av numeriska metoder, informationsbaserad komplexitet , spelteori och statistisk beslutsteori . Föregångare till vad som nu kallas "probabilistisk numerik" kan hittas redan i slutet av 1800-talet och början av 1900-talet.

Ursprunget till probabilistisk numerik kan spåras till en diskussion om probabilistiska metoder för polynominterpolation av Henri Poincaré i hans Calcul des Probabilités . I modern terminologi betraktade Poincaré en Gaussisk förfördelning på en funktion ${\displaystyle f\colon \mathbb {R} \to \mathbb {R} } ,$ uttryckt som en formell potensserie med slumpmässiga koefficienter, och frågade för "troliga värden" av $f(x)$ givet detta föregående och $n\in \mathbb {N}$ observationer $f (a_{i})=B_{i}$ för $i=1,\dots ,n$ .

Ett senare avgörande bidrag till samspelet mellan numerisk analys och sannolikhet gavs av Albert Suldin i samband med univariat kvadratur . Det statistiska problemet som Suldin övervägde var approximationen av den bestämda integralen $\textstyle \int u(t)\,\mathrm {d} t$ för en funktion $u\colon [a,b]\to \mathbb {R}$ , under en Brownsk rörelse före $u$ , ges tillgång till punktvis utvärdering av $u$ vid noderna $t_{1},\dots ,t_{n}\i [a,b]$ . Suldin visade att, för givna kvadraturnoder, är kvadraturregeln med minimalt medelkvadratfel den trapetsformade regeln ; dessutom är detta minimala fel proportionellt mot summan av kuber av avstånden mellan noderna. Som ett resultat kan man se den trapetsformade regeln med lika åtskilda noder som statistiskt optimal i någon mening - ett tidigt exempel på genomsnittsfallsanalys av en numerisk metod. Suldins synvinkel utökades senare av Mike Larkin. Observera att Suldins Brownska rörelse före integranden $u$ är ett gaussiskt mått och att operationerna för integration och punktvis utvärdering av $u$ båda är linjära kartor . Således är den bestämda integralen $\textstyle \int u(t)\,\mathrm {d} t$ en reellt värderad gaussisk slumpvariabel. I synnerhet, efter konditionering på de observerade punktvärdena av $u$ , följer den en normalfördelning med medelvärde lika med trapetsregeln och varians lika med $\textstyle {\frac {1}{12}}\sum _{i=2}^{n}(t_{i}-t_{i-1})^{3}$ . Denna synpunkt ligger mycket nära den Bayesianska kvadraturen , och ser resultatet av en kvadraturmetod inte bara som en punktuppskattning utan som en sannolikhetsfördelning i sig.

Som noterats av Owhadi och medarbetare kan samspelet mellan numerisk approximation och statistisk slutledning också spåras tillbaka till Palasti och Renyi, Sard, Kimeldorf och Wahba (om överensstämmelsen mellan Bayesiansk uppskattning och splineutjämning/interpolation) och Larkin (om korrespondensen mellan Gaussian ) processregression och numerisk approximation). Även om tillvägagångssättet att modellera en perfekt känd funktion som ett urval från en slumpmässig process kan verka kontraintuitivt, kan ett naturligt ramverk för att förstå det hittas i informationsbaserad komplexitet (IBC), grenen av beräkningskomplexitet som bygger på observationen att numerisk implementering kräver beräkning med partiell information och begränsade resurser. I IBC kan prestandan hos en algoritm som arbetar på ofullständig information analyseras i värsta fall eller genomsnittsfall (randomiserad) med avseende på den saknade informationen. Dessutom, som Packel observerade, kunde den genomsnittliga case-inställningen tolkas som en blandad strategi i ett motståndsspel som erhålls genom att lyfta ett (värsta fall) minmax-problem till ett minmax-problem över blandade (randomiserade) strategier. Denna observation leder till ett naturligt samband mellan numerisk approximation och Walds beslutsteori , uppenbarligen påverkad av von Neumanns spelteori . För att beskriva detta samband överväga den optimala återställningsinställningen för Micchelli och Rivlin där man försöker approximera en okänd funktion från ett ändligt antal linjära mätningar på den funktionen. Genom att tolka detta optimala återställningsproblem som ett nollsummespel där spelare I väljer den okända funktionen och spelare II väljer dess approximation, och använder relativa fel i en kvadratisk norm för att definiera förluster, Gaussiska priors framträder som optimala blandade strategier för sådana spel, och kovariansoperatorn för den optimala Gaussiska prioriteten bestäms av den kvadratiska normen som används för att definiera det relativa felet för återhämtningen.

programvara

ProbNum : Probabilistisk numerik i Python.
ProbNumDiffEq.jl : Probabilistiska numeriska ODE-lösare baserade på filtrering implementerade i Julia.
Emukit : Anpassningsbar Python-verktygslåda för beslutsfattande under osäkerhet.
Ryggsäck : Byggd ovanpå PyTorch. Den beräknar effektivt andra kvantiteter än gradienten.

Se även