För alla positiva heltal k, det finns neurala nätverk med  på (k 3 ) lager,  på 1 noder per lager, och  på 1) distinkta parametrar som inte kan approximeras av nätverk med O (k) lager om de inte är exponentiellt stora - de måste ha  på 2 k ) noder. Detta resultat bevisas här för en klass av noder som kallas semi-algebraiska grindar som inkluderar gemensamma val av ReLU, maximal, indikator, och bitvis polynom funktioner, därför att skapa fördelar av djup mot inte bara standardnätverk med ReLU grindar, men också konvolutionella nätverk med ReLU och maximization grindar, sum-produktnätverk, och boosted beslut träd (i detta sista fall med en starkare separation: 2 k 3 ) totala träd noder krävs). Nyckelord: Neurala nätverk, representation, approximation, djuphierarki. Ett neuralt nätverk är en modell av verkligt värderad beräkning definierad av en ansluten riktad graf enligt följande. Noder väntar på reella tal på deras inkommande kanter, därefter datorisera en funktion av dessa reals och överföra den längs deras utgående kanter. Rotnoder tillämpar sin beräkning på en vektor som tillhandahålls som ingång till nätverket, medan interna noder tillämpar sin beräkning på utdata från andra noder. Olika noder kan beräkna olika funktioner, två gemensamma val är maximization gate v → max i v i (där v är vektorn för värden på inkommande kanter), och standard ReLU gate v → σ R ( a, v + b) där σ R (z) := max{0, z} kallas ReLU (rektifierad linjär enhet), och parametrarna a och b kan variera från nod till nod. Grafer i det nuvarande arbetet är acykliska, och det finns exakt en nod utan utgående kanter vars beräkning är utdata från nätverket. Neurala nätverk skiljer sig från många andra funktionsklasser som används i maskininlärning genom att äga flera lager, vilket innebär att utgången är resultatet av att komponera ihop ett godtyckligt antal (potentiellt komplicerade) icke-linjära operationer; däremot, de funktioner som beräknas av boostrade beslut stubbar och SVMs kan skrivas som neurala nätverk med ett konstant antal lager. Syftet med detta arbete är att visa att standardtyper av nätverk alltid vinner i representationskraft med tillägg av lager. Konkret: Det visas att för varje positivt heltal k, det finns neurala nätverk med  på (k 3 ) lager,  på 1) noder per lager, och  på 1) distinkta parametrar som inte kan approximeras av nätverk med O (k) lager och o(2 k ) noder. Innan man anger huvudresultatet, förtjänar ett par val och delar av notation förklaring. För det första använder målet många lager funktion standard ReLU grindar; detta är inte på något sätt nödvändigt, och en mer allmän uttalande kan hittas i Theorem 3.12. För det andra är begreppet approximation L 1 c 2016 M. Telgarsky. TELGARSKY avstånd: med tanke på två funktioner f och g, är deras punktvisa meningsskiljaktighet  till f (x) − g(x) till snitt över kuben [0, 1] d. Även här, samma bevis tillåter flexibilitet (jfr. Teorem 3.12). Slutligen, de grundare nätverk som används för approximation använder semi-algebraiska grindar, som generaliserar de tidigare maximering och standard ReLU grindar, och möjliggöra analys av inte bara standardnätverk med ReLU grindar, men convolutional nätverk med ReLU och maximization grindar (Krizjevsky et al., 2012), summa-produktnätverk (där noder beräkna polynomials) (Poon och Domingos, 2011), och boostrade beslut träd; den fullständiga definitionen av semi-algebraiska grindar visas i Avsnitt 2. Teorem 1.1 Låt alla heltal k ≥ 1 och alla dimensioner d ≥ 1 ges. Det finns f : R d → R beräknas av ett neuralt nätverk med standard ReLU grindar i 2k 3 + 8 lager, 3k 3 + 12 total noder, och 4 + d distinkta parametrar så att där C är föreningen av följande två uppsättningar av funktioner. • Funktioner som beräknas av nätverk av (t, α, β)-halvalgebraiska portar i ≤ k-lager och ≤ 2 k/(tαβ) noder. (T.ex., som med vanliga ReLU-nätverk eller med konvolutionella neurala nätverk med standard ReLU och maximeringsgrindar; cf. Avsnitt 2.) • Funktioner som beräknas genom linjära kombinationer av ≤ t beslutsträd var och en med ≤ 2 k 3 /t noder. (t.ex. den funktionsklass som används av boostrade beslutsträd; jfr. Avsnitt 2.) Analoger till Theorem 1.1 för booleska kretsar - som har booleska ingångar genom {och, eller inte} portar - har studerats i stor utsträckning av kretsens komplexitetsgemenskap, där de kallas djuphierarkiteorem. Seminarieresultatet, på grund av Håstad (1986), fastställer paritetsfunktionens otillnärmelse genom grunda kretsar (såvida deras storlek inte är exponentiell). Standard neurala nätverk verkar ha fått mindre studie; närmast det nuvarande arbetet är en undersökning av Eldan och Shamir (2015) analysera fallet k = 2 när dimensionen d är stor, visar en exponentiell separation mellan 2- och 3-lagers nätverk, en regim som inte hanteras av Theorem 1.1. Ytterligare bibliografiska anteckningar och öppna problem finns i avsnitt 5. Beviset för Theorem 1.1 (och för den mer allmänna Theorem 3.12) upptar avsnitt 3. Nyckelidén är att bara några få funktionskompositioner (lager) räcker för att konstruera en mycket oscillerande funktion, medan funktionstillägg (lägga noder men hålla djupet fast) ger en funktion med få oscillationer. Därefter räcker ett elementärt räkneargument för att visa att low-oscillation funktioner inte kan approxima high-oscillation funktioner. Teorem 1.1 ger bara existensen av ett nätverk (för varje k) som inte kan approximeras av ett nätverk med många färre lager. Det är naturligt att undra om det finns många sådana speciella funktioner. Följande gräns visar att deras befolkning i själva verket är ganska blygsam. Specifikt, konstruktionen bakom Theorem 1.1, som beskrivs i Theorem 3.12, kan ses som att ställa ut O(2 k 3 ) punkter, och en fast märkning av dessa punkter, på vilken ett grunt nätverk knappast förbättras vid slumpmässiga gissningar. Den kommande Theorem 1.2 visar också att även om den enklare uppgiften att montera O(k 9 ) punkter, den tidigare klassen av nätverk är värdelös på de flesta slumpmässiga märkningar. För att ange resultatet är några ytterligare definitioner i sin ordning. För det första är begreppet neurala nätverk mer restriktivt för detta resultat. Låt en neural nettograf G betecknar inte bara grafstrukturen (noder och kanter), men också en tilldelning av grindfunktioner till noder, av kanter till ingångar av grindar, och en tilldelning av fria parametrar w  på R p till parametrarna i portarna. Låt N (G) betecknar den klass av funktioner som erhålls genom att variera de fria parametrarna; denna definition är ganska standard, och diskuteras mer i detalj i avsnitt 2. Som en sista bit av notation, ges en funktion f : Theorem 1.2 Låt alla neurala nettograf G ges med ≤ p parametrar i ≤ l lager och ≤ m total (t, α, β)-semi-algebraiska noder. Därefter för varje δ > 0 och varje n ≥ 8pl 2 ln(8emtαβp(l + 1)) + 4 ln(1/δ) poäng (x i ) n i=1, med sannolikhet ≥ 1 − δ över enhetliga slumpmässiga etiketter Detta bevis är en direkt följd av VC-dimensionen i semi-algebraiska nätverk, som i sin tur kan bevisas genom en liten ändring av VC-dimensionen bevis för styckvis polynom nätverk (Anthony och Bartlett, 1999, Theorem 8,8). Dessutom beror kärnmetoden för VC-dimensiongränser i neurala nätverk på Warren, vars mål var en analog av Theorem 1.2 för polynom (Warren, 1968, Theorem 7). Lemma 1.3 (Förenkling av Lemma 4.2) Låt varje neural nettograf G ges med ≤ p parametrar i ≤ l lager och ≤ m totala noder, som var och en är (t, α, β)-semi-algebraic. Därefter VC(N (G) ≤ 6p(l + 1) ln(2p(l + 1)) + ln(8emtα) + ln(β). Beviset för Theorem 1.2 och Lemma 1.3 finns i avsnitt 4. Argumentet för VC-dimensionen ligger mycket nära argumentet för Theorem 1.1 att ett nätverk med få lager har få svängningar; se avsnitt 4 för vidare diskussion om detta förhållande. Definitionen av en semialgebraisk grind är tyvärr komplicerad; den är utformad för att fånga några standardnoder i en enda abstraktion utan att försämra gränserna. Observera att namnet semialgebraic set är standard (Bochnak et al., 1998, definition 2.1.4), och hänvisar till en uppsättning definieras av fackföreningar och korsningar av polynom ojämlikhet (och därmed namnet missbrukas något här). där U j och L j är undergrupper av [t] (där [t] := {1,.., t}) och p j är ett polynom av grad ≤ β, sådan att En anmärkningsvärd egenskap i definitionen är att antalet termer m inte behöver ange namnet eftersom det inte påverkar någon av komplexitetsskattningarna häri (t.ex., Theorem 1.1 eller Theorem 1.2). Skilda specialfall av semialgebraiska grindar är följande i Lemma 2.3. Standarden bitvis polynom grindar generalisera ReLU och har fått en hel del uppmärksamhet i den teoretiska gemenskapen (Anthony och Bartlett, 1999, Kapitel 8); här en funktion σ : R → R är (t, α)-poly om R kan delas in i ≤ t intervaller så att σ är ett polynom av grad ≤ α inom varje del. Maximerings- och minimeringsgrindarna har blivit populära på grund av deras användning i konvolutionella nätverk (Krizjevsky et al., 2012), som kommer att diskuteras mer i Avsnitt 2.1. Slutligen är beslutsträd och boostrade beslutsträd praktiskt taget framgångsrika klasser som vanligtvis betraktas som konkurrenter till neurala nätverk (Caruana och Niculescu-Mizil, 2006), och har följande struktur. Definition 2.2 Ett k-dt (beslutsträd med k-noder) definieras rekursivt enligt följande. Om k = 1, är det en konstant funktion. Om k > 1, det först utvärderar x → 1[ a, x − b ≥ 0], och därefter villkorligt utvärderar antingen en vänster l-dt eller en höger r-dt där l + r < k. A (t, k)-bdt (boostrat beslut träd) utvärderar x → t i=1 c i g i (x) där varje c i och varje g i är en k-dt. 1. Vad är det för fel på dig? Om σ : R → R är (t, β)-poly och q : R d → R är ett polynom av grad α, sedan standard bitvis polynom grind σ • q är (t, α, αβ)-sa. I synnerhet standard ReLU gate v → σ R ( a, v + b) är (1, 1, 1)-sa. 2. Utgångspunkten är följande: Med tanke på polynomials (p i ) r i=1 av grad ≤ α, standarden (r, α)-min och -max grindar (v) := min i och [r] p i (v) och ί max (v) := max i och [r] q i (v) är (r(r − 1), α, α)-sa. 3. Vad är det som händer? Varje k-dt är (k, 1, 0)-sa, och varje (t, k)-bdt är (tk, 1, 0).
REF visar att det finns ett ReLU-nätverk med L-lager och U = (L)-enheter så att varje nätverk som approximerar det med endast O(L 1/3 )-lager måste ha enheter (2 L 1/3 ); detta fenomen har även för verkligt värderade funktioner.
Benefits of depth in neural networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}