Gaussiska processapproximationer

Inom statistik och maskininlärning är Gaussisk processapproximation en beräkningsmetod som accelererar slutledningsuppgifter inom ramen för en Gaussisk processmodell , oftast sannolikhetsutvärdering och förutsägelse. Liksom approximationer av andra modeller kan de ofta uttryckas som ytterligare antaganden som åläggs modellen, som inte motsvarar någon faktisk egenskap, men som behåller sina nyckelegenskaper samtidigt som de förenklar beräkningar. Många av dessa approximationsmetoder kan uttryckas i rent linjära algebraiska eller funktionella analytiska termer som matris- eller funktionsapproximationer. Andra är rent algoritmiska och kan inte lätt omformuleras som en modifiering av en statistisk modell.

Grundläggande idéer

I statistisk modellering är det ofta bekvämt att anta att ${\displaystyle y\in {\mathcal {Y}}} ,$ fenomenet som undersöks är en Gauss-process indexerad med $X\in {\mathcal {X}}={\mathcal {X}}_{1}\times {\mathcal {X}}_{2}\dots {\mathcal {X}}_{ d}$ som har medelfunktion $\mu :{\mathcal {X}}\rightarrow {\mathcal {Y}}$ och kovariansfunktion $K: {\mathcal {X}}\times {\mathcal {X}}\rightarrow \mathbb {R}$ . Man kan också anta att data $\mathbf {y} =(y_{1},\dots ,y_{n})$ är värden för en viss realisering av denna process för index $\mathbf {X} =X_{1},\dots ,X_{n}$ .

Följaktligen kan den gemensamma distributionen av uppgifterna uttryckas som

$\mathbf {y} \sim {\mathcal {N}}(\mathbf {\mu} ,\mathbf {\Sigma } )$ ,

där $\mathbf {\Sigma } =\left[K(X_{i},X_{j})\right]_{i ,j=1}^{n}$ och ${\displaystyle \mathbf {\mu } =\left(\mu (X_{1}),\mu (X_{2}),\dots ,\mu (X_{d})\right)^{\top }} , dvs en matris med kovariansfunktionsvärdena respektive en$ vektor med medelfunktionsvärdena vid motsvarande (par av) index. Den negativa log-sannolikheten för data tar då formen

$-\log \ell (\mathbf {y}) ={\frac {d}{2\pi }}+{\frac {1}{2}}\log \det(\mathbf {\Sigma } )+\left(\mathbf {y} -\mathbf {\ mu } \right)^{\top }\mathbf {\Sigma } ^{-1}\left(\mathbf {y} -\mathbf {\mu} \right)$

På liknande sätt är den bästa prediktorn för $\mathbf {y} ^{*}$ , värdena för $y$ för index $\mathbf {X} ^{*}=\left(X_{1}^{*},X_{2}^{*},\dots ,X_{d}^{*}\right)$ , given data $\mathbf {y}$ har formen

$\mathbf {\mu} _{\mathbf {y} }^{*}=\mathbb {E} \left[\mathbf {y} ^{*}|\mathbf {y} \right]=\mathbf {\mu} ^{*}-\mathbf {\Sigma } _{\mathbf {y} ^{*}\mathbf {y} }\mathbf {\Sigma } ^{-1}\left(\mathbf {y} -\mathbf {\mu} \right)$

I samband med gaussiska modeller, särskilt inom geostatistik , är förutsägelse med den bästa prediktorn, dvs medelvärde beroende på data, även känd som kriging .

Den beräkningsmässigt dyraste komponenten i den bästa prediktorformeln är att invertera kovariansmatrisen ${\displaystyle \mathbf {\Sigma } } ,$ som har kubisk komplexitet $\displaystyle {\mathcal {O}}(n^{ 3})}$ { . På liknande sätt innebär utvärdering av sannolikhet både att beräkna $\mathbf {\Sigma } ^{-1}$ och determinanten $\det(\mathbf {\Sigma } )$ som har samma kubisk komplexitet.

Gaussiska processapproximationer kan ofta uttryckas i termer av antaganden på $y$ under vilken $\log \ell (\mathbf {y} )$ och $\mathbf {\mu } _{\mathbf {y} }^{*}$ kan beräknas med mycket lägre komplexitet. Eftersom dessa antaganden i allmänhet inte anses spegla verkligheten, är sannolikheten och den bästa prediktorn som erhålls på detta sätt inte exakta, men de är avsedda att ligga nära deras ursprungliga värden.

Modellbaserade metoder

Denna klass av approximationer uttrycks genom en uppsättning antaganden som åläggs den ursprungliga processen och som typiskt sett innebär någon speciell struktur hos kovariansmatrisen. Även om de flesta av dessa metoder utvecklades oberoende, kan de flesta av dem uttryckas som specialfall av den sparsamma allmänna Vecchia-approximationen .

Sparsamma kovariansmetoder

Dessa metoder approximerar den sanna modellen på ett sätt som kovariansmatrisen är sparsam. Vanligtvis föreslår varje metod sin egen algoritm som drar full nytta av sparsitetsmönstret i kovariansmatrisen. Två framträdande medlemmar av denna klass av tillvägagångssätt är kovariansavsmalning och domänpartitionering. Den första metoden kräver i allmänhet ett mått $d$ över ${\mathcal {X}}$ och antar att för ${\displaystyle X,{\tilde {X}}\$ vi har $Cov(y(X),y({\tilde {X}}))\neq 0$ endast om $d(X,{\tilde {X}})<r$ för någon radie $r$ . Den andra metoden antar att det finns ${\mathcal {X}}^{(1)},\dots ,{\mathcal {X}}^{(K) }$ så att $\bigcup _{k=1}^{K}{\mathcal {X}}^{(k)}$ . Sedan med lämplig fördelning av index mellan partitionselement och ordning av element i $X$ är kovariansmatrisen blockdiagonal.

Sparsamma precisionsmetoder

Denna familj av metoder antar att precisionsmatrisen $\mathbf {\Lambda } =\mathbf {\Sigma } ^{-1}$ är sparsam och anger generellt vilka av dess element som inte är noll. Detta leder till snabb inversion eftersom endast dessa element behöver beräknas. Några av de framträdande approximationerna i denna kategori inkluderar tillvägagångssättet baserat på ekvivalensen mellan Gaussiska processer med Matern kovariansfunktion och stokastiska PDEs, periodisk inbäddning och Nearest Neighbor Gauss processer. Den första metoden gäller för fallet med $d=2$ och när ${\mathcal {X}}$ har ett definierat mått och drar fördel av det faktum att Markov-egenskapen gäller vilket gör $\mathbf {\Lambda }$ mycket gles. Den andra utökar domänen och använder Diskret Fourier Transform för att dekorrelera data, vilket resulterar i en diagonal precisionsmatris. Den tredje kräver ett mått på ${\mathcal {X}}$ och drar fördel av den så kallade screeningeffekten förutsatt att $\mathbf {\Lambda } _{i,j }\neq 0$ endast om $d(x_{i},x_{j})<r$ , för vissa $r>0$ .

Glesa Cholesky faktor metoder

I många praktiska tillämpningar ersätts beräkningen av ${\displaystyle \mathbf {\Lambda } } med att först beräkna$${\displaystyle \mathbf {L} } ,$ Cholesky-faktorn för $\mathbf {\Sigma }$ , och sekund dess invers $\mathbf {L} ^{-1}$ . Detta är känt för att vara mer stabilt än en vanlig inversion. Av denna anledning fokuserar vissa författare på att konstruera en sparsam approximation av Cholesky-faktorn för precisions- eller kovariansmatriserna. En av de mest etablerade metoderna i denna klass är Vecchia-approximationen och dess generalisering. Dessa tillvägagångssätt bestämmer den optimala ordningen av index och, följaktligen, elementen i $\mathbf {x}$ och antar sedan en beroendestruktur som minimerar in-fill i Cholesky-faktorn. Flera andra metoder kan uttryckas i detta ramverk, Multi-resolution Approximation (MRA), Nearest Neighbor Gaussian Process, Modified Predictive Process och Full-scale approximation.

Lågrankade metoder

Även om detta tillvägagångssätt omfattar många metoder, är det vanliga antagandet som ligger till grund för dem alla antagandet att ${\displaystyle y} ,$ den Gaussiska processen av intresse, i praktiken är låg. Mer exakt antas det att det finns en uppsättning index ${\bar {X}}=\{{\bar {x}}_{ 1},\dots ,{\bar {x}}_{p}\}$ så att varannan uppsättning index $X=\{x_{1}, \dots ,x_{n}\}$

$y(X)\sim {\mathcal {N}}\left(\mathbf {A} _{X} {\bar {\mathbf {\mu} }},\mathbf {A} _{X}^{\top }{\bar {\mathbf {\Sigma } }}\mathbf {A} _{X}+\ mathbf {D} \right)$

där $\mathbf {A} _{X}$ är en $p\times k$ matris, ${\displaystyle {\bar {\ mathbf {\mu } }}=\mu \left(y\left({\bar {X}}\right)\right)} och Σ ¯ =$ K $\bar { \mathbf {\Sigma } }}=K\left({\bar {X}},{\bar {X}}\right)} och D {\displaystyle \mathbf {$ D $}$ är en diagonal matris. Beroende på metod och tillämpning har olika sätt att välja ${\bar {X}}$ föreslagits. Vanligtvis väljs ${\displaystyle p} för att vara mycket mindre än$${\displaystyle n},$ vilket innebär att beräkningskostnaden för att invertera ${\bar {\mathbf {\Sigma } }}$ är hanterbar ( ${\mathcal {O}}(p^{3})$ istället för ${\displaystyle {\mathcal {O}}(n^{3})} )$ .

Mer generellt, utöver att välja ${\bar {X}}$ , kan man också hitta en $n\times p$ matris $\mathbf {A}$ och anta att $X=\mathbf {A} \mathbf {\eta }$ , där $\mathbf {\eta }$ är $p$ -värden för en Gaussprocess möjligen oberoende av $x$ . Många maskininlärningsmetoder faller inom denna kategori, såsom subset-of-regressors (SoR), relevance vector machine, glesa spektrum Gaussian Process och andra, och de skiljer sig generellt åt i hur de härleder A {\displaystyle \mathbf {A $}$ och $\mathbf {\eta }$ .

Hierarkiska metoder

Den allmänna principen för hierarkiska approximationer består av en upprepad tillämpning av någon annan metod, så att varje på varandra följande applikation förfinar approximationens kvalitet. Även om de kan uttryckas som en uppsättning statistiska antaganden, beskrivs de ofta i termer av en hierarkisk matrisapproximation (HODLR) eller basfunktionsexpansion (LatticeKrig, MRA, wavelets). Den hierarkiska matrismetoden kan ofta representeras som en upprepad tillämpning av en approximation av låg rangordning på successivt mindre delmängder av indexuppsättningen $X$ . Utbyggnad av basfunktioner är beroende av att använda funktioner med kompakt stöd. Dessa funktioner kan sedan utnyttjas av en algoritm som går igenom på varandra följande lager av approximationen. I de mest gynnsamma inställningarna kan några av dessa metoder uppnå kvasilinjär ( ${\displaystyle {\mathcal {O}}(n\log n)})$ komplexitet.

Enhetlig ram

Probabilistiska grafiska modeller ger ett bekvämt ramverk för att jämföra modellbaserade approximationer. I detta sammanhang kan värdet av processen vid index $x_{k}\in X$ sedan representeras av en vertex i en riktad graf och kanter motsvarar termerna i faktoriseringen av fogdensiteten av $y(X)$ . I allmänhet, när inga oberoende samband antas, kan den gemensamma sannolikhetsfördelningen representeras av en godtyckligt riktad acyklisk graf. Att använda en viss approximation kan sedan uttryckas som ett visst sätt att ordna hörn och lägga till eller ta bort specifika kanter.

Metoder utan statistisk modell

Denna klass av metoder specificerar inte en statistisk modell eller lägger antaganden på en befintlig. Tre huvudmedlemmar i denna grupp är meta-kriging-algoritmen, gapfill-algoritmen och Local Approximate Gaussian Process-metoden. Den första delar upp indexuppsättningen i $K$ komponenter ${\mathcal {X}}^{(1)},\dots ,{\mathcal {X}}^{(k)}$ , beräknar den villkorliga fördelningen för var och en av dessa komponenter separat och använder sedan geometrisk median för de villkorliga PDF-filerna för att kombinera dem. Den andra är baserad på kvantilregression med hjälp av värden för processen som ligger nära det värde man försöker förutsäga, där avståndet mäts i termer av ett mått på uppsättningen index. Local Approximate Gaussian Process använder en liknande logik men konstruerar en giltig stokastisk process baserat på dessa närliggande värden.

•   Liu, Haitao; Ong, Yew-Soon; Shen, Xiaobo; Cai, Jianfei (2020). "When Gaussian Process Meets Big Data: A Review of Scalable GPS". IEEE-transaktioner på neurala nätverk och inlärningssystem . PP : 1–19. arXiv : 1807.01065 . doi : 10.1109/TNNLS.2019.2957109 . PMID 31944966 .
•   Heaton, Matthew J.; Datta, Abhirup; Finley, Andrew O.; Furrer, Reinhard; Guinness, Joseph; Guhaniyogi, Rajarshi; Gerber, Florian; Gramacy, Robert B.; Hammerling, Dorit; Katzfuss, Matthias; Lindgren, Finn; Nychka, Douglas W.; Sun, Furong; Zammit-Mangion, Andrew (2018). "En fallstudietävling bland metoder för att analysera stora rumsliga data" . Journal of Agricultural, Biological and Environmental Statistics . 24 (3): 398–425. doi : 10.1007/s13253-018-00348-w . ISSN 1085-7117 .
•   Banerjee, Sudipto (2017). "Högdimensionell Bayesiansk geostatistik" . Bayesiansk analys . 12 (2): 583–614. doi : 10.1214/17-BA1056R . PMID 29391920 .