Universell approximationssats

I den matematiska teorin om artificiella neurala nätverk är universella approximationssatser resultat som fastställer tätheten av en algoritmiskt genererad klass av funktioner inom ett givet funktionsutrymme av intresse. Typiskt gäller dessa resultat approximationsförmågan hos feedforward-arkitekturen på utrymmet av kontinuerliga funktioner mellan två euklidiska utrymmen , och approximationen är med avseende på den kompakta konvergenstopologin .

Det finns emellertid också en mängd olika resultat mellan icke-euklidiska utrymmen och andra ofta använda arkitekturer och, mer allmänt, algoritmiskt genererade uppsättningar av funktioner, såsom den konvolutionella neurala nätverksarkitekturen (CNN), radiella basfunktioner eller neurala nätverk med specifika egenskaper. De flesta universella approximationssatser kan tolkas i två klasser. Den första kvantifierar approximationsförmågan hos neurala nätverk med ett godtyckligt antal artificiella neuroner (" arbitrary width " fall) och den andra fokuserar på fallet med ett godtyckligt antal dolda lager, som vart och ett innehåller ett begränsat antal artificiella neuroner (" arbiträrt djup ") " fall). Utöver dessa två klasser finns det också universella approximationssatser för neurala nätverk med begränsat antal dolda lager och ett begränsat antal neuroner i varje lager (" bounded depth and bounded width" fall).

Universella approximationssatser antyder att neurala nätverk kan representera en mängd olika intressanta funktioner när de ges lämplig vikt. Å andra sidan ger de vanligtvis ingen konstruktion för vikterna, utan anger bara att en sådan konstruktion är möjlig.

Historia

En av de första versionerna av fallet med godtycklig bredd bevisades av George Cybenko 1989 för sigmoidaktiveringsfunktioner . Kurt Hornik, Maxwell Stinchcombe och Halbert White visade 1989 att flerlagers feed-forward-nätverk med så få som ett dolt lager är universella approximatorer. Hornik visade också 1991 att det inte är det specifika valet av aktiveringsfunktionen utan snarare själva flerlagers feed-forward-arkitekturen som ger neurala nätverk potentialen att vara universella approximatorer. Moshe Leshno et al 1993 och senare Allan Pinkus 1999 visade att den universella approximationsegenskapen är likvärdig med att ha en icke-polynomisk aktiveringsfunktion.

Det godtyckliga djupfallet studerades också av ett antal författare, såsom Gustaf Gripenberg 2003, Dmitry Yarotsky, Zhou Lu et al 2017, Boris Hanin och Mark Sellke 2018 och Patrick Kidger och Terry Lyons 2020. 2021, Park et al erhöll den minsta bredd som krävs för den universella approximationen av Lp ^- funktioner med användning av framkopplade neurala nätverk med ReLU som aktiveringsfunktioner. Liknande resultat som kan appliceras direkt på kvarvarande neurala nätverk erhölls också samma år av Paulo Tabuada och Bahman Gharesifard med hjälp av kontrollteoretiska argument.

Fallet avgränsat djup och avgränsad bredd studerades först av Maiorov och Pinkus 1999. De visade att det finns en analytisk sigmoidal aktiveringsfunktion så att två dolda skikts neurala nätverk med begränsat antal enheter i dolda skikt är universella approximatorer. Med hjälp av algoritmer och datorprogrammeringstekniker, konstruerade Guliyev och Ismailov en smidig sigmoidal aktiveringsfunktion som ger universell approximationsegenskap för två dolda lager framåtkopplade neurala nätverk med färre enheter i dolda lager. Det bevisades konstruktivt i 2018 års papper att nätverk med enstaka dolda lager med begränsad bredd fortfarande är universella approximatorer för univariata funktioner, men denna egenskap är inte längre sant för multivariabla funktioner.

Det finns flera förlängningar av satsen, som till diskontinuerliga aktiveringsfunktioner, icke-kompakta domäner, certifierbara nätverk, slumpmässiga neurala nätverk och alternativa nätverksarkitekturer och topologier.

Fall med godtycklig bredd

En mängd uppsatser under 1980--1990-talet, från George Cybenko och Kurt Hornik etc, etablerade flera universella approximationssatser för godtycklig bredd och begränsat djup. Se för recensioner. Följande är det som oftast citeras:

Universal approximationssats — Låt $C(X,Y)$ beteckna uppsättningen av kontinuerliga funktioner från $X$ till $Y$ . Låt $\sigma \in C(\mathbb {R} ,\mathbb {R} )$ . Observera att ${\displaystyle (\sigma \circ x)_{i}=\sigma (x_{i})} ,$ så $\sigma \circ x$ betecknar $\sigma$ applicerad på varje komponent av $x$ .

Då är $\sigma$ inte polynom om och bara om för varje ${\displaystyle n\in \mathbb {N} } ,$ m $\displaystyle m\in \mathbb {N} }$ , kompakt $K\subseteq \mathbb {R} ^{n}$ , $f\in C(K,\mathbb {R} ^{ m}),\varepsilon >0$ det finns $k\in \mathbb {N}$ , $A\in \mathbb {R} ^{k\times n }$ , $b\in \mathbb {R} ^{k}$ , $C\in \mathbb {R} ^{m\times k}$ sådana den där

\sup _{x\in K}\|f(x)-g(x)\|<\varepsilon

var

g(x)=C\cdot (\sigma \circ (A\cdot x+b))

En sådan $f$ kan också approximeras av ett nätverk med större djup genom att använda samma konstruktion för det första skiktet och approximera identitetsfunktionen med senare skikt.

Bevisskiss

Det räcker för att bevisa fallet där $m=1$ , eftersom enhetlig konvergens i $\mathbb {R} ^{m}$ bara är enhetlig konvergens i varje koordinat.

Låt $F_{\sigma }$ vara mängden av alla neurala nätverk med ett dolda lager konstruerade med $\sigma$ . Låt $C_{0}(\mathbb {R} ^{d},\mathbb {R} )$ vara mängden av alla $C( \mathbb {R} ^{d},\mathbb {R} )$ med kompakt stöd.

Om funktionen är ett polynom av grad $d$ , så finns ${\displaystyle F_{\sigma }} i det stängda delrummet av alla polynom med grad$ $d$ , så dess stängning är också som finns i den, vilket inte är allt av $C_{0}(\mathbb {R} ^{d},\mathbb {R} )$ .

Annars visar vi att $F_{\sigma }$ s stängning är hela $C_{0}(\mathbb {R} ^{d},\mathbb { R} )$ . Antag att vi kan konstruera godtyckligt bra approximationer av rampfunktionen $r(x)={\begin{cases}-1{\text{ if }}x<-1\\x{\text{ if }}|x|\leq 1 \\1{\text{ om }}x>1\\\end{cases}}$ så kan den kombineras för att konstruera godtycklig kompakt-stödd kontinuerlig funktion till godtycklig precision. Det återstår att approximera rampfunktionen.

Vilken som helst av de vanligaste aktiveringsfunktionerna som används i maskininlärning kan uppenbarligen användas för att approximera rampfunktionen, eller först approximera ReLU, sedan rampfunktionen.

om $\sigma$ är "squashing", det vill säga den har gränser $\sigma (-\infty )<\sigma (+\infty )$ , då kan man först affint skala ner dess x-axel så att dess graf ser ut som en stegfunktion med två skarpa "överskjutningar", sedan göra en linjär summa av tillräckligt många för att göra en "trappuppgång" approximation av rampfunktionen. Med fler steg i trappan jämnas överskotten ut och vi får en godtyckligt bra approximation av rampfunktionen.

Fallet där $\sigma$ är en generisk icke-polynomfunktion är svårare, och läsaren riktas till.

Problemet med polynom kan tas bort genom att tillåta utdata från de dolda lagren att multipliceras tillsammans ("pi-sigma-nätverken"), vilket ger generaliseringen:

Universell approximationssats för pi-sigma-nätverk — Med alla icke-konstant aktiveringsfunktioner är ett ett-dolt pi-sigma-nätverk en universell approximator.

Godtyckligt djupfall

De "dubbla" versionerna av satsen tar hänsyn till nätverk av begränsad bredd och godtyckligt djup. En variant av den universella approximationssatsen bevisades för det godtyckliga djupfallet av Zhou Lu et al. 2017. De visade att nätverk med bredd n+4 med ReLU- aktiveringsfunktioner kan approximera vilken Lebesgue-integrerbar funktion som helst på n -dimensionellt inmatningsutrymme med avseende på $L^{1}$ avstånd om nätverksdjupet tillåts växa . Det visades också att om bredden var mindre än eller lika med n , gick denna allmänna uttryckskraft att approximera en Lebesgue-integrerbar funktion förlorad. I samma artikel visades det att ReLU- nätverk med bredd n+1 var tillräckliga för att approximera alla kontinuerliga funktioner av n -dimensionella indatavariabler. Följande förfining specificerar den optimala minimibredden för vilken en sådan approximation är möjlig och beror på.

Universell approximationssats (L1-avstånd, ReLU-aktivering, godtyckligt djup, minimal bredd). För alla Bochner–Lebesgue p-integrerbara funktioner ${\displaystyle f:\mathbb {R} ^{n}\rightarrow \mathbb {R} ^{m}} och valfri ϵ >$ { $\ epsilon >0}$ , det finns ett helt anslutet ReLU- nätverk $F$ med bredd exakt $d_{m}=\max\{{n+1} ,m\}$ , tillfredsställande

$\int _{\mathbb {R} ^{n}}\left\|f(x)-F_{}(x )\right\|^{p}\mathrm {d} x<\epsilon$ .

Dessutom finns det en funktion $f\in L^{p}(\mathbb {R} ^{n},\mathbb {R} ^{m})$ och några $\epsilon >0$ , för vilka det inte finns något helt anslutet ReLU- nätverk med en bredd som är mindre än $d_{m}=\max\{ {n+1},m\}$ som uppfyller ovanstående approximationsgräns.

Kvantitativ förfining: I det fall när ${\mathcal {X}}=[0,1]^{d}$ och $D=1$ och där $\sigma$ är ReLU-aktiveringsfunktionen , då är det exakta djupet och bredden för ett ReLU-nätverk för att uppnå $\varepsilon$ -felet också känt. Om dessutom målfunktionen $f$ är jämn, kan det erforderliga antalet lager och deras bredd vara exponentiellt mindre. Även om $f$ inte är jämn, kan dimensionalitetens förbannelse brytas om f medger ytterligare "kompositionsstruktur".

Tillsammans ger det centrala resultatet av följande universella approximationssats för nätverk med begränsad bredd (jfr även för det första resultatet av detta slag).

Universell approximationssats (Uniform icke- affin aktivering, godtyckligt djup , begränsad bredd). Låt ${\mathcal {X}}$ vara en kompakt delmängd av $\mathbb {R} ^{d}$ . Låt $\sigma :\mathbb {R} \to \mathbb {R}$ vara vilken icke- affin kontinuerlig funktion som helst som är kontinuerligt differentierbar vid åtminstone en punkt, med icke- nollderivata vid den punkten. Låt ${\mathcal {N}}_{d,D:d+D+2}^{\sigma }$ beteckna utrymmet för framkopplade neurala nätverk med $d$ ingångsneuroner, $D$ utgångsneuroner och ett godtyckligt antal dolda lager var och en med $d+D+2$ neuroner, så att varje dold neuron har aktivering funktion $\sigma$ och varje utgångsneuron har identiteten som sin aktiveringsfunktion, med ingångslager $\phi$ och utgångslager $\rho$ . Sedan ges valfritt $\varepsilon >0$ och valfritt $f\in C({\mathcal {X}},\mathbb {R} ^{D})$ , det finns ${\hat {f}}\i {\mathcal {N}}_{d,D:d+D+2}^ {\sigma }$ så att

$\sup _{x\in {\mathcal {X}}}\,\left\|{\hat {f}}(x)-f(x)\right\|<\varepsilon .$

Med andra ord, ${\mathcal {N}}$ är tät i $C({\mathcal {X}};\mathbb {R} ^{D})$ med avseende på topologin för enhetlig konvergens .

Kvantitativ förfining: Antalet lager och bredden av varje lager som krävs för att approximera f till $\varepsilon$ känd precision; Dessutom gäller resultatet när ${\mathcal {X}}$ och $\mathbb {R} ^{D}$ ersätts med valfritt icke-positivt krökt Riemann-grenrör .

Vissa nödvändiga villkor för fallet med begränsad bredd, godtyckligt djup har fastställts, men det finns fortfarande ett gap mellan de kända tillräckliga och nödvändiga villkoren.

Avgränsat djup och avgränsat breddfall

Det första resultatet om approximationsförmåga hos neurala nätverk med begränsat antal lager, som var och en innehåller ett begränsat antal artificiella neuroner, erhölls av Maiorov och Pinkus. Deras anmärkningsvärda resultat avslöjade att sådana nätverk kan vara universella approximatorer och för att uppnå denna egenskap räcker två dolda lager.

Universell approximationssats: Det finns en aktiveringsfunktion $\sigma$ som är analytisk, strikt ökande och sigmoidal och har följande egenskap: För alla ${\displaystyle f\in C[0$ och $\varepsilon >0$ det finns konstanter $d_{i},c_{ij},\theta _ {ij},\gamma _{i}$ och vektorer $\mathbf {w} ^{ij}\in \mathbb {R} ^{d}$ för vilka

$\left\vert f(\mathbf {x} )-\sum _{i=1}^{6d+3}d_{i}\sigma \left(\sum _{j=1}^ {3d}c_{ij}\sigma (\mathbf {w} ^{ij}\cdot \mathbf {x-} \theta _{ij})-\gamma _{i}\right)\right\vert <\ varepsilon$
för alla $\mathbf {x} =(x_{1},...,x_{d})\i [0, 1]^{d}$ .

Detta är ett existensresultat. Det sägs att aktiveringsfunktioner som tillhandahåller universell approximationsegenskap för avgränsade djupbegränsade breddnätverk existerar. Med hjälp av vissa algoritmer och datorprogrammeringstekniker konstruerade Guliyev och Ismailov effektivt sådana aktiveringsfunktioner beroende på en numerisk parameter. Den utvecklade algoritmen gör att man kan beräkna aktiveringsfunktionerna när som helst på den verkliga axeln direkt. För algoritmen och motsvarande datorkod se. Det teoretiska resultatet kan formuleras enligt följande.

Universell approximationssats: Låt $[a,b]$ vara ett ändligt segment av den reella linjen, $s=ba$ och $\lambda$ vara någon Positivt nummer. Sedan kan man algoritmiskt konstruera en beräkningsbar sigmoidal aktiveringsfunktion ${\displaystyle \sigma \colon \mathbb {R} \to \mathbb {R} } ,$ som är oändligt differentierbar, strikt ökar på $(-\infty ,s)$ , $\lambda$ -strikt ökande på $[s,+\infty )$ , och uppfyller följande egenskaper:

1) För alla $f\in C[a,b]$ och $\varepsilon >0$ finns det nummer $c_{1},c_{2},\theta _{1}$ och $\theta _{2}$ så att för alla $x\in [a, b]$
$|f(x)-c_{1}\sigma (x-\theta _{1})-c_{2}\sigma (x-\theta _{2})|<\varepsilon$
2) För varje kontinuerlig funktion $F$ på $d$ -dimensionella rutan $[a,b]^{d}$ och $\varepsilon >0$ , det finns konstanter $e_{p}$ , $c_{pq}$ , $\theta _{pq}$ och $\ zeta _{p}$ så att ojämlikheten
$\left|F(\mathbf {x} )-\sum _{p=1}^{2d+2}e_{p}\sigma \left(\sum _{q=1}^{ d}c_{pq}\sigma (\mathbf {w} ^{q}\cdot \mathbf {x} -\theta _{pq})-\zeta _{p}\right)\right|<\varepsilon$ gäller för alla $\mathbf {x} =(x_{1},\ldots ,x_{d})\i [a,b ]^{d}$ . Här är vikterna $\mathbf {w} ^{q}$ , $q=1,\ldots ,d$ fixerade enligt följande: $\mathbf {w} ^{1}=(1,0,\ldots ,0),\quad \mathbf {w} ^{2}=(0,1,\ldots ,0),\quad \ ldots ,\quad \mathbf {w} ^{d}=(0,0,\ldots ,1).$ Dessutom är alla koefficienter ${\displaystyle e_{p}} ,$ förutom en, lika.

Här betyder $\lambda$ $\sigma \colon \mathbb {R} \to \mathbb {R}$ λ -strikt ökande på någon uppsättning ${\displaystyle X} ”$ det finns en strikt ökande funktion $u\colon X\to \mathbb {R}$ så att $|\sigma (x)-u(x)|\leq \lambda$ för alla $x\in X$ . Uppenbarligen fungerar en $\lambda$ -ökande funktion som en vanlig ökande funktion när $\lambda$ blir liten. I " depth-width "-terminologin säger ovanstående sats att för vissa aktiveringsfunktioner är djup- $2$ width- $2$ -nätverk universella approximatorer för univariata funktioner och djup- $3$ width- ${\displaystyle (2d+2)}-$ nätverk är universella approximatorer för $d$ -variabelfunktioner ( ${\displaystyle d>1})$ .

Grafinmatning

Att uppnå användbar universell funktionsapproximation på grafer (eller snarare på grafisomorfismklasser ) har varit ett långvarigt problem. De populära grafkonvolutionella neurala nätverken (GCNs eller GNNs) kan göras lika diskriminerande som Weisfeiler-Lemans grafisomorfismtest. $O (}$ approximationssatsresultat av Brüel-Gabrielsson, som visar att grafrepresentation med vissa injektiva egenskaper är tillräcklig för universell funktionsapproximation på avgränsade grafer och begränsad universell funktionsapproximation på obegränsade grafer, med ett åtföljande O ( {\ #edges $\times$ #nodes $)$ -körningsmetod som presterade vid toppmoderna på en samling benchmarks.

Se även