Sammanfattning av denna webbsida: Papperet karakteriserar grupper av funktioner för vilka djupt lärande kan vara exponentiellt bättre än ytligt lärande. Djupa konvolutionsnät är ett specialfall av dessa villkor, även om viktdelning inte är den främsta orsaken till deras exponentiella fördel. Detta arbete stöddes av Center for Brains, Minds and Machines (CBMM), finansierat av NSF STC-utmärkelsen CCF -1231216. H.M. stöds delvis av ARO Grant W911NF-15-1-0385. Sammanfattning av denna webbsida: Papperet karakteriserar grupper av funktioner för vilka djupt lärande kan vara exponentiellt bättre än ytligt lärande. Djupa konvolutionsnät är ett specialfall av dessa villkor, även om viktdelning inte är den främsta orsaken till deras exponentiella fördel. Nyckelord: Deep and Shallow Networks, Convolutional Neural Networks, Funktion Tillnärmning, Deep Learning 1 En teori om deep learning Det finns tre huvuduppsättningar teorifrågor om Deep Neural Networks. Den första uppsättningen frågor handlar om kraften i arkitekturen - vilka klasser av funktioner kan det approxima och lära sig väl? Den andra uppsättningen frågor handlar om inlärningsprocessen: varför är SGD (Stochastic Gradient Descent) så orimligt effektivt, åtminstone till utseende? Den tredje, viktigare frågan handlar om generalisering. Överparametrisering kan förklara varför minima är lätta att hitta under träningen, men varför verkar överutrustning vara mindre ett problem än för klassiska grunda nätverk? Är detta på grund av att djupa nätverk är mycket effektiva algoritmer för hierarkisk Vector Quantization? I detta dokument fokuserar vi särskilt på den första uppsättningen frågor, sammanfatta flera teorem som har dykt upp online 2015 [1, 2, 3], och 2016 [4, 5]. Därefter beskriver vi ytterligare resultat samt några gissningar och öppna frågor. Huvudbudskapet är att djupa nätverk har den teoretiska garanti, som ytliga nätverk inte har, att de kan undvika dimensionellitetens förbannelse för en viktig klass av problem, som motsvarar kompositionsfunktioner, det vill säga funktioner. En särskilt intressant undergrupp av sådana kompositionsfunktioner är hierarkiskt lokala kompositionsfunktioner där alla de ingående funktionerna är lokala i betydelsen begränsad liten dimensionalitet. De djupa nätverk som kan approximera dem utan dimensionalitetens förbannelse är av den djupa konvolutionstypen (även om viktdelning inte är nödvändig). Konsekvenserna av de teorem som sannolikt kommer att vara relevanta i praktiken är: 1. Vissa djupa konvolutionella arkitekturer har en teoretisk garanti för att de kan vara mycket bättre än ett lager arkitekturer såsom kärnmaskiner; 2. de problem för vilka vissa djupa nätverk garanteras att undvika förbannelsen av dimensionalitet (se för en trevlig granskning [6] ) motsvarar input-output kartläggningar som är kompositionella. Den mest intressanta uppsättningen av problem består av kompositionsfunktioner som består av en hierarki av ingående funktioner som är lokala: ett exempel är f (x1, · · ·, x8) = h3(h21(h11(x1, x2), h12(x3, x4)), h22(h13(x5, x6), h14(x7, x8)). Den sammansatta funktionen f kräver endast "lokala" beräkningar (här med rättvis dimension 2) i var och en av dess ingående funktioner h; 3. den centrala aspekten av konvolutionella nätverk som kan ge dem en exponentiell fördel är inte viktdelning utan lokalitet på varje nivå i hierarkin. Deep Learning referenser börjar med Hintons backpropagation och med Lecuns convolutional nätverk (se för en trevlig recension [7] ). Naturligtvis har flerlagers konvolutionsnät funnits åtminstone så långt tillbaka som 70-talets optiska processtid. Neocognitron [8] var ett konvolutionellt neuralt nätverk som tränades att känna igen karaktärer. Kompositionalitetens egenskap var en huvudmotivation för hierarkiska modeller av visuell cortex såsom HMAX som kan betraktas som en pyramid av AND och OR lager [9], det är en sekvens av associationer och disjunktioner. Flera uppsatser på 80-talet fokuserade på approximationskraft och inlärningsegenskaper hos ett dolda nät (s.k. grunt nätverk här). Mycket lite dök upp på flerskiktsnät, (men se [10 11, 12] ), främst på grund av att ett dolt lager nät utfördes empiriskt såväl som djupare nätverk. På den teoretiska sidan drar Pinkus 1999 [13] slutsatsen att "... det verkar finnas anledning att anta att den två dolda lagermodellen kan vara betydligt mer lovande än den enda dolda lagermodellen...". En version av frågorna om hierarkiernas betydelse ställdes i [14] enligt följande: "En jämförelse med verkliga hjärnor erbjuder en annan, och förmodligen relaterad, utmaning för inlärningsteorin. De "lärande algoritmer" som vi har beskrivit i detta dokument motsvarar arkitekturer i ett lager. Är hierarkiska arkitekturer med fler skikt försvarbara när det gäller inlärningsteori? Det verkar som om inlärningsteorin av den typ vi har beskrivit inte erbjuder några allmänna argument till förmån för hierarkiska inlärningsmaskiner för regression eller klassificering. Detta är något av ett pussel eftersom organisationen av cortex - till exempel visuell cortex - är starkt hierarkisk. Samtidigt visar hierarkiska inlärningssystem överlägsen prestanda i flera tekniska tillämpningar." På grund av den stora empiriska framgången med djupt lärande under de senaste tre åren har flera dokument behandlat frågan om varför hierarkier har framträtt. Sum-Product nätverk, som är likvärdiga med polynom nätverk (se [15, 16] ), är ett enkelt fall av en hierarki som analyserades [17] men inte gav särskilt användbara insikter. Montufar och Bengio [18] visade att antalet linjära regioner som kan syntetiseras av ett djupt nätverk med ReLU-linjäritet är mycket större än av ett grunt nätverk. Innebörden av detta resultat i termer av approximation teori och av våra resultat är för närvarande en öppen fråga 1. Relevant för denna översyn är arbetet med hierarkiska kvadratiska nätverk [16], tillsammans med resultat funktion approximation [19, 13]. Också relevant är Shashuas gissning (se [20] ) om en förbindelse mellan djupinlärningsnätverk och de hierarkiska Tucker-representationerna av tensorer. I själva verket beskriver våra teorem formellt den klass av funktioner för vilka hypotesen gäller. Detta dokument beskriver och utökar resultaten pre- 1 Vi antar att resultatet kan likna andra exempel i avsnitt 4.2. Den säger att det bland de funktioner som är styckvis linjära finns funktioner som kan syntetiseras genom djupa nätverk med ett visst antal enheter men som kräver ett mycket stort antal enheter som ska syntetiseras av grunda nätverk som sänds i [21, 22, 23] och [24, 4] som härleder nya övre gränser för tillnärmning genom djupa nätverk av vissa viktiga kategorier av funktioner som undviker dimensionellitetens förbannelse. Den övre gränsen för approximationen av grunda nätverk av allmänna funktioner var välkänd för att vara exponentiell. Det verkar naturligt att anta att, eftersom det inte finns något allmänt sätt för grunda nätverk att utnyttja en komposition tidigare, lägre gränser för tillnärmning av grunda nätverk av kompositionsfunktioner också bör vara exponentiellt. I själva verket har Telgarsky [25] och Shamir [26] nyligen gett exempel på specifika funktioner som inte på ett effektivt sätt kan representeras av grunda nätverk. Vi tillhandahåller i Theorem 5 ytterligare ett exempel på en klass av kompositionsfunktioner för vilka det finns ett gap mellan grunda och djupa nätverk. I detta avsnitt anger vi teorem om de approximativa egenskaperna hos grunda och djupa nätverk. Det allmänna paradigmet är som följer. Vi är intresserade av att bestämma hur komplext ett nätverk bör vara för att teoretiskt garantera approximation av en okänd målfunktion f upp till en given noggrannhet > 0. För att mäta noggrannheten behöver vi en norm · på någon normerad linjär rymd X. Som vi kommer att se den norm som används i resultaten av detta dokument är supnormen i enlighet med standardvalet i approximationsteorin. Lägg emellertid märke till att den relevanta normen för maskininlärning är L2-normen. I detta avseende är flera av våra resultat starkare än vad som behövs. Å andra sidan kräver våra huvudsakliga resultat på kompositionalitet su normen för att vara oberoende från den okända distributionen av indata. Detta är viktigt för maskininlärning. Låt VN vara den uppsättning av alla nätverk av ett givet slag med komplexitet N som vi tar här för att vara det totala antalet enheter i nätverket (t.ex. alla grunda nätverk med N enheter i det dolda lagret). Det antas att den klass av nät med högre komplexitet omfattar dem med lägre komplexitet, dvs. VN  på VN+1. Graden av approximation definieras av dist(f, VN ) = inf (1) γ ) kommer att vara tillräcklig för att garantera en approximation med noggrannhet minst. Eftersom f är okänt, för att få teoretiskt bevisade övre gränser, måste vi göra vissa antaganden om den funktionsklass från vilken den okända målfunktionen väljs. Denna en priori information kodifieras genom uttalandet att f  på W för vissa subrymd W  på X. Denna subrymd är vanligtvis en jämnhetsklass som kännetecknas av en jämnhetsparameter m. Här generaliseras den till en jämnhet och kompositionsklass, som kännetecknas av parametrarna m och d (d = 2 i exemplet i figur 1; i allmänhet är kärnans storlek i ett konvolutionsnätverk). Detta avsnitt karakteriserar förhållanden under vilka djupa nätverk är "bättre" än grunt nätverk i approximering av funktioner. Således jämför vi grunda (ett dolt skikt) nätverk med djupa nätverk som visas i Figur 1. Båda typerna av nätverk använder samma små uppsättning av operationer - punkt produkter, linjära kombinationer, en fast icke-linjär funktion av en variabel, eventuellt convolution och pooling. Varje nod i de nätverk vi anser motsvarar vanligtvis en nod i diagrammet för den funktion som ska approximeras, som visas i figuren. I synnerhet varje nod i nätverket innehåller ett visst antal enheter. En enhet är en neuron som beräknar var w är vektorn för vikter på vektorns ingång x. Både t och det verkliga antalet b är parametrar stämda genom inlärning. Vi antar här att varje nod i nätverken beräknar den linjära kombinationen av r sådana enheter Observera att för vårt huvudexempel av ett djupt nätverk som motsvarar en binär trädkurva, den resulterande arkitekturen är en idealiserad version av den uppsjö av djupa konvolutionella neurala nätverk som beskrivs i litteraturen. I synnerhet har det bara en output på toppen till skillnad från de flesta av de djupa arkitekturer med många kanaler och många toppnivåutgångar. Motsvarar, varje nod beräknar ett enda värde i stället för flera kanaler, med hjälp av kombinationen av flera enheter (se Ekvation 3 ). Vårt tillvägagångssätt och grundläggande resultat gäller snarare direkt för mer komplexa nätverk (se tredje anmärkningen i avsnitt 6). En noggrann analys och jämförelse med simuleringar kommer att beskrivas i det framtida arbetet. Logiken i våra teorem är som följer. • Både grunda (a) och djupa (b) nätverk är universella, det vill säga de kan approximera godtyckligt alla kontinuerliga funktioner av n variabler på en kompakt domän. Resultatet för grunda nätverk är klassiskt. Eftersom grunda nätverk kan ses som ett specialfall av djupa nätverk, det klart att för varje kontinuerlig funktion av n variabler, finns det också ett djupt nätverk som approximerar funktionen godtyckligt väl på en kompakt domän. • Vi anser att en speciell klass av funktioner av n variabler på en kompakt domän som är en hierarkisk sammansättning av lokala funktioner såsom strukturen av funktionen i ekvation 4 representeras av en graf av binär trädtyp. Detta är det enklaste exemplet på kompositionsfunktioner, som återspeglar dimensionalitet d = 2 för de ingående funktionerna h. I allmänhet är d godtyckligt men fast och oberoende av dimensionaliteten n i kompositionsfunktionen f. I våra resultat kommer vi ofta att tänka på n ökar medan d är fast. I avsnitt 4 kommer vi att överväga det mer allmänna kompositionsfallet. • Tillnärmning av funktioner med en sammansättning struktur - kan uppnås med samma grad av noggrannhet genom djupa och grunda nätverk men att antalet parametrar är mycket mindre för de djupa nätverken än för det grunda nätet med motsvarande approximation noggrannhet. Det är intuitivt att ett hierarkiskt nätverk som matchar strukturen i en kompositionsfunktion bör vara "bättre" på att approximera det än ett generiskt grunt nätverk, men universalitet av grunda nätverk kräver icke-uppenbara karakterisering av "bättre". Vårt resultat klargör att intuitionen verkligen är korrekt. Bild 1 De översta graferna är kopplade till funktioner; vart och ett av de nedre diagrammen visar det ideala nätverket som approximerar funktionen ovan. I a) ett grunt universellt nätverk i 8 variabler och N enheter approximerar en generisk funktion av 8 variabler f (x1, · · · ·, x8). Insättning b) visar ett binärt träd hierarkiskt nätverk längst ner i n = 8 variabler, som ungefär motsvarar väl funktioner av formen f (x1, · · ·, x8) = h3(h21(h11(x1, x2), h12(x3, x4)), h22(h13(x5, x6), h14(x7, x8)) som representeras av den binära grafen ovan. I det approximerande nätverket motsvarar var och en av n − 1 noderna i grafen på funktionen en uppsättning Q = N=1 ReLU-enheter som beräknar åsfunktionen Varje term i åsfunktionen motsvarar en enhet i noden (detta skiljer sig något från dagens djupa nätverk, men motsvarar dem, se text och notera i 6). I ett binärt träd med n-ingångar finns log2n-nivåer och totalt n − 1 noder. Likt det grunda nätet är ett hierarkiskt nätverk universellt, dvs. det kan approximera alla kontinuerliga funktioner; texten bevisar att det kan approximera en kompositionsfunktioner exponentiellt bättre än ett grunt nätverk. Ingen variation - det är viktdelning - antas här. Lägg märke till att den viktigaste egenskapen som gör konvolutionella djupnät exponentiellt bättre än ytliga för sammansättningsfunktioner är lokaliseringen av de ingående funktionerna - det är deras låga dimensionalitet. Viktdelning motsvarar alla ingående funktioner på samma nivå (h11 = h12 etc.). Infälld c) visar en annan mekanism som kan utnyttjas av det djupa nätverket i botten för att minska förbannelsen av dimensionalitet i kompositionsfunktionen i toppen: utnyttja olika grader av jämnhet av de ingående funktionerna, se Theorem 6 i texten. Observera att i c) måste ingångsdimensionen vara ≥ 2 för att de djupa näten ska ha en fördel framför de grunda näten. De enklaste exemplen på funktioner som ska beaktas för a), b) och c) är polynom med en struktur som motsvarar grafen överst. I det fortsatta maskininlärningen antar vi att de grunda nätverken inte har någon strukturell information om den funktion som skall läras (här dess sammansättningsstruktur), eftersom de inte kan representera den direkt och inte kan utnyttja fördelen med ett mindre antal parametrar. I vilket fall som helst, inom ramen för approximationsteorin, kommer vi att uppvisa och citera lägre gränser för approximation genom grunda nätverk för klassen av kompositionsfunktioner. Djupa nätverk med standardarkitekturer å andra sidan representerar kompositionalitet i deras arkitektur och kan anpassas till detaljerna i sådan förhandsinformation. Vi ungefärliga funktioner av n variabler i form av ekvation (4) med nätverk där aktiveringen icke-linjäritet är en utjämnad version av den så kallade ReLU, ursprungligen kallas ramp av Breiman och ges av σ(x) = x+ = max(0, x). Arkitekturen av de djupa nätverken reflekterar ekvation (4) med varje nod hi är en ås funktion, som består av en eller flera neuroner. vara utrymmet för alla kontinuerliga funktioner på I n, med f = maxx tillIn (x) till. Låt SN,n betecknar klassen av alla grunda nätverk med N enheter i formen Antalet utbildningsbara parametrar här är (n + 2)N  på n. Låt m ≥ 1 vara ett heltal, och W n m vara uppsättningen av alla funktioner av n variabler med kontinuerliga partiella derivat av order upp till m < ❌ sådan att f där D k betecknar den partiella derivatan som indikeras av multiinteger k ≥ 1, och W n m är summan av komponenterna i k. För hierarkiska binära trädnätverk, definieras de analoga utrymmena genom att betrakta den kompakta uppsättningen W n,2 m som klass av alla kompositionsfunktioner f av n variabler med binär trädarkitektur och konstituerande funktioner h i W 2 m. Vi definierar motsvarande klass av djupa nätverk DN,2 att vara uppsättningen av alla djupa nätverk med en binär träd arkitektur, där var och en av de ingående noderna är i SM,2, där N =  till V, V är uppsättningen av icke-blad hörn av trädet. Vi noterar att i fallet när n är ett heltal effekt på 2, det totala antalet parametrar inblandade i ett djupt nätverk i DN,2 -det vill säga, vikter och fördomar, är 4N. Två observationer är avgörande för att förstå innebörden av våra resultat: • kompositionsfunktioner av n variabler är en delmängd av func- m. Djupa nätverk kan utnyttja i sin arkitektur den speciella strukturen av kompositionsfunktioner, medan grunda nätverk är blinda för det. Med tanke på de grunda nätverken är funktioner i W n,2 m bara funktioner i W n m. Detta är inte fallet för de djupa nätverken. • Det djupa nätverket behöver inte ha exakt samma sammansättningsarkitektur som den sammansättningsfunktion som ska approximeras. Det räcker att den acykliska graf som representerar funktionens struktur är en del av grafen som representerar det djupa nätets struktur. Graden av approximativa uppskattningar beror på grafen som är kopplad till nätverket och är därmed en övre gräns för vad som skulle kunna uppnås med ett nätverk som exakt motsvarar funktionsarkitekturen. Följande två teorem uppskattar graden av approximation för grunda och djupa nätverk. Det första teoremet handlar om grunda nätverk. Teorin 1. Låt σ : R → R vara oändligt olika, och inte ett polynom. För f  på W n m komplexiteten hos grunda nätverk som ger noggrannhet minst är -n/m ) och är det bästa möjliga. Noter I [27, Theorem 2.1], Theorem anges under förutsättning att σ är oändligt olika, och det finns b  till R sådan att σ (k) (b) = 0 för alla heltal k ≥ 0. Det bevisas i [28] att det andra villkoret är likvärdigt med att σ inte är ett polynom. Beviset i [27] bygger på det faktum att algebraiska polynom i n-variabler av (totalt eller koordinatmässigt) grad < q under dessa förhållanden är i den enhetliga stängningen av spännvidden för O(q n ) funktioner i formen x → σ( w, x + b) (se tillägg 4.1). Uppskattningen själv är en övre gräns för graden av approximation av sådana polynom. Eftersom den bygger på approximationen av polynomutrymmet i åsfunktionerna som genomförs av grunda nätverk, kan man fråga sig om den skulle kunna förbättras genom att använda ett annat tillvägagångssätt. Svaret bygger på begreppet ickelinjär n-bredd för den kompakta uppsättningen W n m (jfr. [29, 4)............................................................................................................ De n-bredd resultat innebär att uppskattningen i Theorem (1) är den bästa möjliga bland alla rimliga [29] metoder för att approximera godtyckliga funktioner i W n m. Uppskattningen av Theorem 1 är det bästa möjliga om den enda en priori information vi tillåts anta är att målfunktionen tillhör f  på W n m. Det exponentiella beroendet av dimension n av antalet -n/m av parametrar som behövs för att erhålla en noggrannhet O( ) är känd som förbannelsen av dimensionalitet. Observera att de konstanter som är involverade i O i teorem kommer att bero på normerna för derivat av f samt σ. En enkel men användbar följd av beviset för Theorem 1 om polynom (som är ett mindre utrymme än utrymmen av Sobolev funktioner). Låt oss beteckna med P n k det linjära utrymmet av polynom av grad som mest k i n variabler. Sen hörs 1. Låt σ : R → R vara oändligt olika, och inte ett polynom. Varje f P n k kan realiseras med en godtycklig noggrannhet av grunt nätverk med r-enheter, r = n+k k... k n. Vår andra och huvudsakliga teorem handlar om djupa nätverk med jämna aktiveringar och är nyligen (preliminära versioner dök upp i [3, 2, 4] ). Vi formulerar det i det binära träd fallet för enkelhet men det sträcker sig omedelbart till funktioner som är sammansättningar av ingående funktioner av ett fast antal variabler d istället än av d = 2 variabler som i beskrivningen av teorem (i konvolutionella nätverk d motsvarar storleken på kärnan). m överväga ett djupt nätverk med samma kompositonal arkitektur och med en aktiveringsfunktion σ : R → R som är oändligt olika, och inte ett polynom. Komplexiteten i nätverket för att ge approximation med noggrannhet minst är bevis för att bevisa Theorem 2, vi observera att var och en av de ingående funktionerna i W 2 m, (1) tillämpas med n = 2 innebär att var och en av dessa funktioner kan approximeras från SN,2 upp till noggrannhet = cN -m/2. Vårt antagande att f  på W N,2 m innebär att var och en av dessa funktioner är Lipschitz kontinuerlig. Därför är det lätt att dra slutsatsen att, till exempel, om P, P1, P2 är approximationer till de ingående funktionerna h, h1, h2, respektive inom en noggrannhet av Sedan eftersom för vissa konstant c > 0 oberoende av de funktioner som berörs. Detta, tillsammans med det faktum att det finns (n - 1) noder, leder till (6). Även i detta fall bevis ger följande korollary om undergruppen T n k av utrymmet P n k som består av kompositionella polynomials med en binär träd graf och ingående polynom funktioner av grad k (i 2 variabler) Corollary 2. Låt σ : R → R vara oändligt olika, och inte ett polynom. Låt n = 2 l. Då f T n k kan realiseras av ett djupt nätverk med ett binärt träd diagram och totalt r enheter med r = (n − 1) Det är viktigt att betona att antagandena om σ i teorem inte är nöjda med ReLU-funktionen x → x+, men de är nöjda genom att jämna ut funktionen i ett godtyckligt litet intervall runt ursprunget. Detta tyder på att resultatet av teorem bör vara giltigt även för icke-smooth ReLU. Avsnitt 4.1 ger formella resultat. Starkare resultat än teorem i detta avsnitt (se [5] ) innehas för nätverk där varje enhet utvärderar en Gaussisk icke-linjäritet, dvs. Gaussiska nätverk av formen där approximationen är på hela Euclidean utrymme. Sammanfattningsvis, när den enda en priori antagande om målfunktionen handlar om antalet derivat, sedan för att garantera en noggrannhet av, Vi behöver ett grunt nätverk med O ( −n/m ) utbildningsbara parametrar. Om vi antar en hierarkisk struktur på målfunktionen som i Theorem 2, då motsvarande djupa nätverk ger en garanterad noggrannhet med O ( −2/m ) trainingable parametrar. Observera att Theorem 2 gäller för alla f med en kompositionsarkitektur som ges av en graf som motsvarar, eller är en del av, grafen som är associerad med det djupa nätverket - i detta fall grafen som motsvarar W n,d m. Theorem 2 leder naturligt till begreppet effektiv dimensionalitet som vi formaliserar i nästa avsnitt Definition 1. Den effektiva dimensionen av en funktionsklass W (för en viss norm) sägs vara d om någon funktion i W för varje > 0, kan återställas inom en noggrannhet av (mätt med normen) med hjälp av ett lämpligt nätverk (antingen grunt eller djupt) med −d parametrar. Den huvudsakliga funktionsklassen som vi betraktade i tidigare artiklar består av funktioner som i figur 1 b som vi kallade kompositionsfunktioner. Termen "kompositionalitet" användes med den betydelse den har i språk och syn, där begrepp på högre nivå består av ett litet antal lägre nivåer, objekt består av delar, meningar består av ord och ord består av stavelser. Lägg märke till att den här betydelsen av kompositionalitet är smalare än den matematiska betydelsen av funktionernas sammansättning. De kompositionsfunktioner som vi har beskrivit i tidigare uppsatser kan mer exakt kallas funktioner som består av hierarkiskt lokala funktioner. Här generaliserar vi formellt våra tidigare resultat till den bredare klassen av kompositionsfunktioner (bortom den hierarkiska lokaliteten i figur 1b till figur 1c och figur 2 ) genom att formellt upprepa några kommentarer från tidigare papper. Låt oss börja med ett av de tidigare exemplen. Överväg +F y 2 + 2Gx + 2Hy + I) Eftersom Q är nominellt ett polynom av koordinatmässigt grad 2 11, [27, Lemma 3.2] visar att ett grunt nätverk med 2 11 + 1 enheter kan approximera Q godtyckligt väl på I 2. Men på grund av den hierarkiska strukturen av Q, [27, Lemma 3.2] visar också att ett hierarkiskt nätverk med 9 enheter kan approximera det kvadratiska uttrycket, och 10 ytterligare lager, var och en med 3 enheter kan approximera de på varandra följande makterna. Således kan ett hierarkiskt nätverk med 11 lager och 39 enheter approximera Q godtyckligt väl. Vi noterar att även om Q är nominellt av grad 2 11, var och en av de monomial koefficienter i Q är en funktion av endast 9 variabler, A, · · · ·, I. Ett annat exempel är Detta är uppenbarligen en Lipschitz kontinuerlig funktion av 2 variabler. Den effektiva dimensionen av denna klass är 2, och därför skulle ett grunt nätverk kräva minst c −2 parametrar för att approxima den inom. Den effektiva dimensionen av klassen univariat Lipschitz kontinuerliga funktioner är dock 1. Därför, om vi tar hänsyn till det faktum att Q är en sammansättning av ett polynom av grad 2 i 2 variabler och den univariat Lipschitz kontinuerlig funktion t →  på, då är det lätt att se att samma approximation kan uppnås genom att använda ett tvåskiktat nätverk med O( −1 ) parametrar. För att formulera vårt mest allmänna resultat som inkluderar exemplen ovan samt den hierarkiska lokalitetens begränsning definierar vi först formellt en kompositionsfunktion i form av en riktad acyklisk graf. Låt G vara en riktad acyklisk graf (DAG), med uppsättningen av noder V. En G-funktion definieras enligt följande. Varje källa nod får en inmatning från R. Varje in-kant av varje annan nod representerar en indata realvariabel, och noden själv representerar en funktion av dessa indata verkliga variabler, som kallas en komponentfunktion. De utkanter fläktar ut resultatet av denna utvärdering. Vi antar att det bara finns en diskbänksnod, vars utgång är G-funktionen. Därför, ignorera sammansättningen av denna funktion, är det en funktion av n variabler, där n är antalet källnoder i G. Theorem 3. Låt G vara en DAG,n vara antalet källnoder, och för varje v  på V, Låt dv vara antalet in-kanter av v. Låta f : R n → R vara en kompositionell G-funktion, där var och en av de konstituerande funktionen är i W dv mv. Betrakta grunda och djupa nätverk med oändligt jämn aktiveringsfunktion som i Theorem 1. Sedan djupa nätverk - med en tillhörande graf som motsvarar grafen f - undvika förbannelsen av dimensionalitet i tillnärmning f för att öka n, medan grunda nätverk inte direkt kan undvika förbannelsen. I synnerhet är komplexiteten hos det bästa approximerande grunda nätet exponentiell i n Figur 2 Figuren visar diagram över funktioner som kan ha liten effektiv dimensionalitet, beroende på det antal enheter per nod som krävs för god approximation. där m = minv på V mv, medan komplexiteten i det djupa nätverket är följande definition 1 kallar vi dv/mv den effektiva dimensionen av funktion v. Då, djupa nätverk kan undvika förbannelsen av dimensionalitet om de ingående funktionerna i en kompositionsfunktion har en liten effektiv dimension; d.v.s. har fast, "liten" dimensionalitet eller fast, "liten" "roughness. En annan tolkning av Theorem 3 är följande. Förslag 1. Om en funktionsfamilj f : R n → R av jämnhet m har en effektiv dimension < n/m, då funktionerna är sammansatta på ett sätt som överensstämmer med uppskattningarna i Theorem 3. Observera att de funktioner som ingår i detta teorem är funktioner som antingen är lokala eller sammansättningen av enklare funktioner eller båda. Figur 2 visar några exempel utöver exemplen högst upp i figur 1. Som tidigare, det finns en enkel korollary för polynom funktioner: Corollary 3. Låt σ : R → R vara oändligt olika, och inte ett polynom. Med uppsättningen som i Theorem 3, låt f vara DAG polynom; d.v.s. en DAG-funktion, var och en av vars ingående funktioner är ett polynom av grad k. Då f kan representeras av ett djupt nätverk med O( skaVN  på d ) enheter, där  på VN är antalet icke-blad hörn, och d är den maximala ingraden av noderna. Till exempel, om G är en hel binär träd med 2 n blad, då den nominella graden av G polynom som i Corollary 3 är k Observera att polynomials i S n k är glesa med ett antal termer som inte är exponentiellt i n, det vill säga det är inte O (k n ) men linjär i n (som är O (nk)) eller som mest polynomial i n. Resultaten vi beskrev hittills använda smidig aktiveringsfunktioner. Vi har redan nämnt varför vi inte bör ändra våra resultat på ett grundläggande sätt om vi avslappar antagandet om smidighet. Medan studier på egenskaperna hos neurala nätverk med smidig aktivering i överflöd, resultaten på icke-smooth aktiveringsfunktioner är mycket mer sparsamma. Här kommer vi helt kort ihåg några av dem. När det gäller grunda nätverk kan tillståndet för en smidig aktiveringsfunktion avlastas för att bevisa densitet (se [13], Proposition 3.7): Förslag 2. Låta σ =: R → R vara i C 0, och inte ett polynom. Sedan grunda nätverk är täta i C 0. I synnerhet, åsfunktioner med hjälp av ReLUs av formen r i=1 ci( wi, x + bi)+, med wi, x  på R n, ci, bi  på R är täta i C. Nätverk med icke-smooth aktiveringsfunktioner förväntas göra relativt dåligt i approximering smidiga funktioner såsom polynomials i sup norm. "Bra" grad av approximationsgrad (modulo a konstant) har bevisats i L2-normen. Definiera B enheten bollen i R n. Ring C m (B n ) uppsättningen av alla kontinuerliga funktioner med kontinuerlig derivat upp till grad m definieras på enheten bollen. Vi definierar Sobolevrymden W med avseende på Sobolevnormen p (se för detaljer [13] sidan 168). Vi definierar utrymmet B Det visas i [13, Corollary 6.10] att dessa approximationsresultat med avseende på L 2 normen inte kan tillämpas för att härleda gränser för kompositionsnätverk. I det senare fallet behövs, som vi redan påpekat, uppskattningar i den enhetliga normen för att kontrollera spridningen av felen från det ena skiktet till det andra, se Theorem 2. Resultat i denna riktning ges i [30], och på senare tid i [31] och [5] (se Theorem 3.1). Framför allt är det möjligt att med hjälp av ett resultat i [31] och enligt bevisstrategin i Theorem 2 få fram följande resultat på approximationen av Lipshitz kontinuerliga funktioner med djupa och grunda ReLU-nätverk som efterliknar vårt Theorem 2: Theorem 4. Låt f vara en L-Lipshitz kontinuerlig funktion av n variabler. Sedan, komplexiteten i ett nätverk som är en linjär kombination av ReLU som ger en approximation med noggrannhet åtminstone är var det i en djup komposition arkitektur är Vår allmänna Theorem 3 kan utökas på ett liknande sätt. Teorem 4 är ett exempel på hur analysen av smidiga aktiveringsfunktioner kan anpassas till ReLU. Den visar i själva verket hur djupa kompositionsnätverk med standardiserade ReLU kan undvika dimensionalitetens förbannelse. I ovanstående resultat kvantifieras funktionens regelbundenhet av storleken på Lipshitz konstant. Om det senare är den bästa idén om smidighet för ReLU-baserade nätverk, och om ovanstående uppskattningar kan förbättras, är intressanta frågor som vi skjuter upp till ett framtida arbete. Ett resultat som är mer intuitivt och som kan återspegla vad nätverk faktiskt gör beskrivs i bilaga 4.3. Även om den konstruktion som beskrivs där ger approximation i L2-normen men inte i supnormen, är detta inte ett problem under någon diskretisering av det reella antal som krävs för datorsimuleringar (se tillägget). Figur 3, 4, 5, 6 ger en sundhetskontroll och empiriskt stöd för våra huvudsakliga resultat och för påståendena i inledningen. Det finns flera enheter per nod av trädet. I vår inställning här nätverket med en tillhörande binärt träd graf sattes upp så att varje lager hade samma antal enheter och delade parametrar. Antalet enheter för det grunda och binära trädet neurala nätverk hade samma antal parametrar. Till vänster är funktionen sammansatt av en enda ReLU per nod och approximeras av ett nätverk med ReLU-aktiveringar. På höger sida är kompositionsfunktionen f (x1, x2, x3, x4) = h2(h11(x1, x2), h12(x3, x4)) och approximeras av ett nätverk med en jämn ReLU-aktivering (även kallad softplus). Funktionerna h1, h2, h3 är som beskrivs i figur 3. För att ligga nära arbetets approximationsfall användes en stor datamängd på 60K-utbildningsexempel för båda utbildningsseten. Vi använde SGD Adams [32] optimizer. För att få den bästa möjliga lösningen körde vi 200 oberoende hyper parameter sökningar med slumpmässig sökning [33] och rapporterade den med det lägsta träningsfelet. Hyperparametrarna sökningen var över stegstorleken, sönderfallsfrekvensen, frekvensen av sönderfall och mini-batch storlek. Den exponentiella sönderfall hyper parametrar för Adam var fast till de rekommenderade värdena enligt den ursprungliga papper [32]. Genomförandet baserades på TensorFlow [34]. Figuren visar på toppen grafen av funktionen som ska approximeras, medan den nedre delen av figuren visar ett djupt neuralt nätverk med samma grafstruktur. Den vänstra och högra noden inf det första lagret har varje n enheter vilket totalt ger 2n enheter i det första lagret. Det andra skiktet har totalt 2n enheter. Det första skiktet har en konvolution av storlek n för att spegla strukturen av den funktion som ska läras. Den sammansättningsfunktion vi ungefär har formen f (x1, x2, x3, x4) = h2(h11(x1, x2), h12(x3, x4)) med h11, h12 och h2 som anges i figuren. Hittills har vi visat att det finns djupa nätverk - till exempel av den konvolutionella typen - som kan undvika dimensionalitetens förbannelse om de funktioner de lär sig är välsignade med kompositionalitet. Det finns ingen liknande garanti för grunda nätverk: för grunda nätverk som approximerar generiska kontinuerliga funktioner är de nedre och övre gränserna båda exponentiella [13]. När det gäller maskininlärning är det uppenbart att grunda nätverk, till skillnad från djupa nätverk, inte i sin arkitektur kan utnyttja det minskade antalet parametrar i samband med tidigare funktioner som motsvarar kompositionsfunktioner. I tidigare artiklar har vi listat några exempel, varav några också är giltiga lägre gränser ur approximationsteorins synvinkel: • Polynomet som tidigare bedömts kan approximeras genom djupa nätverk med ett mindre antal parametrar än grunda nätverk bygger på polynomisk approximering av funktioner av typen g(g())). Här finns dock inga formella bevis för att det är omöjligt att uppnå en god tillnärmning genom grunda nätverk. För en lägre gräns behöver vi åtminstone ett exempel på en kompositionsfunktion som inte kan approximeras av grunda nätverk med en icke-exponentiell grad av approximation. • Ett sådant exempel, för vilket ett bevis på den nedre gränsen finns sedan några decennier, överväga en funktion som är en linjär kombination av n tensor produkt Chui-Wang spline wavelets, där varje våget är en tensor produkt cubic spline. Det visas i [11, 12] som är omöjligt att genomföra en sådan funktion med hjälp av ett grunt neuralt nätverk med en sigmoidal aktiveringsfunktion med hjälp av O(n) neuroner, men ett djupt nätverk med aktiveringsfunktion (x+) 2 kan göra det. I detta fall finns det, som vi nämnde, ett formellt bevis på en klyfta mellan djupa och grunda nätverk. På liknande sätt visar Eldan och Shamir [35] andra fall med separationer som är exponentiella i inmatningsdimensionen. • Som vi nämnde tidigare, Telgarsky visar en exponentiell klyfta mellan vissa funktioner som produceras av djupa nätverk och deras approximation av grunda nätverk. Teorem [25] kan sammanfattas som att säga att en viss familj av klassificeringsproblem med verkligt värderade ingångar inte kan approximeras väl av grunda nätverk med färre än exponentiellt många noder medan ett djupt nätverk uppnår nollfel. Detta motsvarar högfrekvent, gles trigonometrisk polynom i vårt fall. Hans övre gräns kan bevisas direkt från vår huvudsakliga teorem genom att överväga den real-värderade polynom x1x2...x d definieras på kuben (−1, 1) d som uppenbarligen är en kompositionsfunktion med en binär trädkurva. • Vi visar här ett annat exempel för att illustrera en begränsning av grunda nätverk i approximering av en kompositionsfunktion. Låt n ≥ 2 vara ett heltal, B  till R n vara enheten bollen av R n. Vi anser att klass W av alla kompositionsfunktioner f = f2 • f1, där f1 : R n → R, och  på k till≤4 där AN är antingen klass SN av alla grunda nätverk med N-enheter eller DN av djupa nätverk med två lager, den första med n ingångar, och den nästa med en ingång. De båda fallen är aktiveringsfunktionen en C-funktion σ : R → R som inte är ett polynom. Däremot finns det c3 > 0 sådana att konstanterna c1, c2, c3 kan bero på n. PROOF. Uppskattningen (12) följer av de uppskattningar som redan gjorts för de djupa näten. För att bevisa (11) använder vi Lemma 3.2 i [12]. Låta vara en C-funktion som stöds på [0, 1] och vi anser att fN (x) =  och 4 N x på 2 ). Vi kan tydligt välja så att fN ∞ = 1. Då är det klart att varje fN  på W. Helt klart, Vi väljer (14) Eftersom fN stöds på {x  på R n :  på x på ≤ 4 −N }, kan vi imitera beviset på Lemma 3.2 in [12] med g * k (t) = σ(t+b * k ). Låt x0  och B vara sådana att (utan förlust av allmängiltighet) fN (x0) = maxx på B, fN (x) och μ0 vara dirac-måttet som stöds vid x0. Vi grupperar {w * k } i m = N/ (n − 1) separata grupper av n − 1 vektorer vardera. För varje grupp, vi tar vektorer {v } sådan att v är ortogonal till w * k's i grupp. Argumentet i beviset för Lemma 3.2 i [12] kan ändras för att få ett mått μ med total variation 2 m så att det är lätt att här utläsa som i [12] med hjälp av dualitetsprincipen som tillsammans med (13) och (14) innebär (11). Så vid det här laget finns det gott om exempel på lägre gränser som visar en klyfta mellan grunda och djupa nätverk. Ett särskilt intressant fall är produktfunktionen, det vill säga monomial f (x1, · · · ·, xn) = x1x2 · · · xn vilket ur vår synvinkel är de prototypiska sammansättningsfunktionerna. Med tanke på frågan om lägre gränser, frågan här har att göra med minsta heltal r(n) sådan att funktionen f är i stängningen av spännvidden av σ( w k, x + b k ), med k = 1, · · ·, r(n) och w k, b k sträcker sig över hela sina domäner. Ett sådant resultat har hävdats när det gäller smidiga intermodala lastenheter, med hjälp av ovanliga grupptekniker och skisseras i tillägget till [36]. Observera, till stöd för gissningen, att förutsatt att ett grunt nätverk med (icke-smooth) ReLUs har en lägre gräns av r(q) = O(q) kommer att leda till en uppenbar motsägelse med Hastad teorem (som handlar om representation inte approximation av Booleska funktioner) genom att begränsa xi från xi  och (-1, 1) till xi {‐1, +1}. Hastad-teoremet [37] fastställer att paritetsfunktionen inte kan tillnärmas genom grunda kretsar av icke-exponentiell storlek. Som redan nämnts behöver det ungefärliga djupa nätverket inte exakt matcha arkitekturen för kompositionsfunktionen så länge grafen eller trädet som hör ihop med funktionen finns i grafen som hör ihop med nätverket. Detta är naturligtvis goda nyheter: den kompositionalitet som tidigare inbäddats i nätverkets arkitektur återspeglar inte exakt grafen i en ny funktion som ska läras. Vi har visat att för en viss klass av kompositionsfunktioner som kännetecknas av en tillhörande graf finns det ett djupt nätverk som approximerar en sådan funktion bättre än ett grunt nätverk. Samma nätverk approximerar väl funktioner som kännetecknas av subgrafer av den ursprungliga klassen. Bevisen på våra teorem visar att linjära kombinationer av kompositionsfunktioner är universella i den meningen att de kan approximera alla funktioner och att djupa nätverk med ett antal enheter som ökar exponentiellt med lager kan approximera alla funktioner. Observera att djupt sammansatta nätverk kan interpolera om de överparametriseras med avseende på data, även om data återspeglar en icke-kompositionell funktion. Observera å andra sidan att den enklaste kompositionsfunktionen -addition - är trivial i den meningen att den inte erbjuder någon approximativ fördel för de djupa nätverken. Nyckelfunktionen är multiplikation vilket är för oss de prototypiska kompositionsfunktionerna. Som en följd av detta är polynom funktioner kompositionella - de är linjära kombinationer av monomials som är kompositionella. Deras sammansättning ger dock ingen fördel när det gäller tillnärmning, på grund av det exponentiella antalet sammansättningstermer. Som vi nämnde tidigare, nätverk som motsvarar grafer som innehåller grafen av den funktion som ska läras kan utnyttja kompositionalitet. Det relevanta antalet parametrar som ska optimeras är dock antalet parametrar r i nätverket och inte antalet parametrar r * (r * < r) i det optimala djupa nätverket med en graf exakt matchad med grafen i funktionen som ska läras. Som en åt sidan, det pris som ska betalas i att använda en icke-optimal tidigare beror på inlärningsalgoritmen. Till exempel, under gleshet begränsningar kan det vara möjligt att betala ett mindre pris än r (men högre än r * ). I detta avseende kan vissa av de tätt sammankopplade djupa nätverk som används i praktiken – som innehåller glesa grafer som kan vara relevanta för den funktion som ska läras och som fortfarande är "mindre" än det exponentiella antalet enheter som krävs för att representera en generisk funktion av n-variabler – i vissa fall kunna utnyttja en underliggande kompositionsstruktur utan att betala ett orimligt pris i form av den komplexitet som krävs. Det tillvägagångssätt som används i våra huvudteoréer föreslår följande överväganden (se bilaga 1 för en kort inledning). Strukturen av ett djupt nätverk återspeglas i polynomials som bäst approximeras av det -till exempel generiska polynomials eller gles polynomials (i koefficienterna) i d variabler i ordning k. Trädstrukturen i noderna i ett djupt nätverk återspeglar strukturen av en specifik gles polynomial. Generisk polynom av grad k i d variabler är svåra att lära eftersom antalet termer, utbildningsbara parametrar och tillhörande VC-dimension är alla exponentiella i d. Å andra sidan, funktioner approximerade väl av gles polynomials kan läras effektivt genom djupa nätverk med en trädstruktur som matchar polynom. Vi minns att på ett liknande sätt flera egenskaper hos vissa Booleska funktioner kan "läsas ut" från villkoren i deras Fourier expansion som motsvarar "stora" koefficienter, det vill säga från ett polynom som approximerar väl funktionen. Klassiska resultat [37] om djupbreddsbytet i kretsarnas design visar att djupa kretsar är effektivare när det gäller att representera vissa booleska funktioner än grunda kretsar. Hastad visade att mycket varierande funktioner (i betydelsen att ha höga frekvenser i sitt Fourier-spektrum), särskilt paritetsfunktionen inte ens kan vara anständigt approximerad av små konstanta djupkretsar (se även [38] ). Ett närbesläktat resultat följer omedelbart från vår huvudteoretik eftersom funktioner av verkliga variabler i formen x1x2... Observera att Hastads resultat på Booleska funktioner ofta har citerats till stöd för påståendet att djupa neurala nätverk kan representera funktioner som grunda nätverk inte kan. Till exempel skriver Bengio och LeCun [39] "Vi hävdar att de flesta funktioner som på ett kompakt sätt kan representeras av djupa arkitekturer inte kan representeras av en kompakt grund arkitektur". Slutligen vill vi nämna några andra observationer om Booleska funktioner som visar en intressant koppling till vår strategi. Det är känt att inom Booleska funktioner AC 0 klass av polynom storlek konstanta djup kretsar kännetecknas av Fourier transformer där det mesta av effektspektrum är i låg ordning koefficienter. Sådana funktioner kan approximeras väl genom ett polynom av låg grad och kan läras väl genom att endast överväga sådana koefficienter. Det finns två algoritmer [40] som gör det möjligt att lära sig av vissa Booleska funktionsklasser: 1. den lågorderalgoritm som approximerar funktioner genom att beakta deras låga ordning Fourier koefficienter och 2. den glesa algoritmen som lär sig en funktion genom att approximera dess signifikanta koefficienter. Beslutslistor och beslutsträd kan läras av den första algoritmen. Funktioner med liten L1 norm kan approximeras väl av den andra algoritmen. Booleska kretsar som uttrycker DNFs kan approximeras av den första men ännu bättre av den andra. I många fall kan en funktion tillnärmas av en liten uppsättning koefficienter, men dessa koefficienter motsvarar inte lågordertermer. Alla dessa fall överensstämmer med noterna om glesa funktioner i avsnitt 6. Den viktigaste egenskapen hos teorin om kompositionsfunktioner skissade här är att vissa djupa nätverk kan lära dem att undvika förbannelsen av dimensionalitet på grund av välsignelsen av kompositionalitet via en liten effektiv dimension. Här redogör vi för flera kommentarer och antaganden. • Antaganden av kompositionalitetstypen kan få mer direkta praktiska konsekvenser och vara minst lika effektiva som antaganden om funktionsmjukhet när det gäller att motverka dimensionalitetens förbannelse när det gäller lärande och tillnärmning. • Beräkningarna av n-bredden innebär att det finns någon funktion i antingen W n m (teori 1) eller W n,2 m (teori 2) för vilken approximationen inte kan vara bättre än den som föreslås i teorierna. • Den viktigaste frågan som kan ställas om relevansen av de teoretiska resultaten av detta papper och nätverk som används i praktiken har att göra med de många "kanaler" som används i det senare och med vårt antagande att varje nod i nätverken beräknar en skalarfunktion - den linjära kombinationen av r-enheter (ekvation 3). Följande uppenbara men intressanta utvidgning av Theorem 1 till vektor-värderade funktioner säger att antalet dolda enheter som krävs för en given noggrannhet i varje komponent av funktionen är samma som i skalor fallet som beaktas i våra teorem (naturligtvis antalet weigths är större): Corollary 4. Låt σ : R → R vara oändligt olika, och inte ett polynom. För en vektorvärderad funktion f : R n → R q med komponenter fi  på W n m, i = 1, · ·, q antalet dolda enheter i grunda nätverk med n ingångar, q utgångar som ger noggrannhet minst i var och en av komponenterna i f är demonstrationen följer beviset för teorem 1, se även tillägg 4.1. Det innebär att inse att de dolda enheter (eller linjära kombinationer av dem) kan vara likvärdiga med monomials av en generisk polynom av grad k i n variabler som kan användas av en annan uppsättning koefficienter för var och en av fi. Detta argument betyder naturligtvis inte att det är vad som händer när man lär sig detta; det ger ett sätt att utföra approximationen och en tillhörande övre gräns. Den corollary ovan leder till ett enkelt argument som generaliserar våra binära träd resultat till standard, flera kanaler djupa konvolutionella nätverk genom att införa en uppsättning virtuella linjära enheter som ouputs av ett lager och ingångar av nästa. Detta i sin tur leder till följande förutsägelse: För konsekvent approximation noggrannhet över lagren, bör rangen av vikterna matriser mellan enheter i på varandra följande lager ha en rang i storleksordningen av antalet dimensionalitet i det första lagret (ingångar och utgångar måste definieras wrt stöd för konvolution kärnan). Detta tyder på rangnedsättande viktmatriser i nuvarande nätverk. • Vi har använt polynom (men se bilaga 4.3) för att bevisa resultat om komplexiteten av approximation i fallet med neurala nätverk. Neurala nätverk lärande med SGD kan eller får inte syntetisera polynom, beroende på smidigheten i aktiveringsfunktionen och på målet. Detta är inte ett problem för att teoretiskt fastställa övre gränser för graden av konvergens, eftersom resultaten med hjälp av ramen på ickelinjär bredd garanterar att de "polynomiska" gränserna är optimala. • Både ytliga och djupa representationer kan eller kanske inte reflektera invarians till gruppomvandlingar av ingångar av funktionen ( [41, 22] ). Invarians - också kallad viktdelning - minskar komplexiteten i nätverket. Eftersom vi är intresserade av jämförelsen av grunda vs djupa arkitekturer, har vi övervägt det generiska fallet av nätverk (och funktioner) för vilka invariant inte antas. I själva verket är den viktigaste fördelen med djupt kontra grunt nätverk - vilket bevisas av beviset för theorem - den tillhörande hierarkiska lokaliteten (de ingående funktionerna i varje nod är lokala som har en liten dimensionalitet) och inte varians (som betecknar delade vikter som är noder på samma nivå som delar samma funktion). Man kan då fråga om förhållandet mellan dessa resultat och i-teori [42]. Den ursprungliga kärnan i i-teorin beskriver hur pooling kan ge antingen grunda eller djupa nätverk med invarians och selektivitet egenskaper. Varians hjälper naturligtvis, men inte exponentiellt som hierarkisk lokalitet gör. • Det finns flera egenskaper som följer av teorin här som är attraktiva ur neurovetenskapens synvinkel. En av de viktigaste är att resultaten är robusta när det gäller valet av ickelinjära egenskaper (linjära likriktare, sigmoider, Gaussians etc.) och poolar. • I en maskininlärning sammanhang, minimering över en utbildning uppsättning av en förlustfunktion såsom kvadratförlust ger en empirisk approximation av regressionsfunktionen p (y/x). Vår hypotes om komposition blir en hypotes om strukturen på den villkorliga sannolikhetsfunktionen. • Tänk på igen fallet med avsnitt 4 av en multivariat funktion f : [0, 1] d → R. Antag att diskretisera det genom en uppsättning styckvis konstant splines och deras tensor produkter. Varje koordinat ersätts effektivt av n booleanska variabler.Detta resulterar i en d-dimensionell tabell med N = n d poster. Detta motsvarar i sin tur en booleansk funktion f : {0, 1} N → R. Här motsvarar antagandet om kompositionalitet kompressibiliteten hos en d-dimensionell tabell i termer av en hierarki av d − 1 2-dimensionella tabeller. I stället för n d poster finns (d − 1) n 2 poster. Detta har i sin tur uppenbara samband med HVQ (Hierarchical Vector Quantization), diskuteras i bilaga 5. • Som bilaga 4.3 visar kan varje funktion f approximeras med en epsilon-stängd binärfunktion fB. Binarisering av f : R n → R görs genom att använda k partitioner för varje variabel xi och indikatorfunktioner. Således f → fB : {0, 1} kn → R och sup på − fB till ≤, med beroende på k och avgränsad Df. • fB kan skrivas som ett polynom (en Walsh nedbrytning) fB  på pB. Det är alltid möjligt att associera en p b till någon f, givet. • Binarization argumentet föreslår ett direkt sätt att ansluta resultat på funktion approximation av neurala nät med äldre resultat på Booleska funktioner. De senare är specialfall av de tidigare resultaten. • Man kan tänka på tensorer när det gäller d-dimensionella tabeller. Ramen för hierarkiska nedbrytningar av tensorer - särskilt det hierarkiska Tucker-formatet - är nära kopplad till vår uppfattning om kompositionalitet. Intressant nog har den hierarkiska upplösningen av Tucker varit föremål för senaste tidens uppsatser om Deep Learning (t.ex. se [20] ). Detta arbete, liksom mer klassiska tidningar [43], karakteriserar inte direkt den klass av funktioner för vilka dessa nedbrytningar är effektiva. Notera att tensor nedbrytningar antar att summan av polynom funktioner i ordning d är gles (se ekv. högst upp på sidan 2030 av [43] ). Våra resultat ger en rigorös grund för det tensoriska arbete som har att göra med djup inlärning. Det finns uppenbarligen en mängd intressanta kopplingar till approximationsteorin som bör utforskas. Observera att begreppet separation grad av en tensor är mycket nära relaterad till den effektiva r i ekvation 26. • Vi föreslår att definiera binär sparhet f, i termer av glesheten i den booleska funktionen pB; binär sparhet innebär att en approximation till f kan läras av icke-exponentiella djupa nätverk via binarization. Lägg märke till att om funktionen f är kompositionell är de tillhörande Booleska funktionerna fB glesa; det motsatta är inte sant. • I kan situationer, Tikhonov legalisering motsvarar skära hög ordning Fourier koefficienter. Koefficienternas sparsamhet underställer Tikhonovs legalisering vid en Fourier-representation. Notera att som en effekt antalet Fourier koefficienter minskas, det vill säga trainingable parametrar, i den ungefärliga trigonometric polynomial. Sparhet Fourier koefficienter är en allmän begränsning för att lära Booleska funktioner. • Sparsamhet på en särskild grund. En uppsättning funktioner kan definieras för att vara sparsamma i en specifik grund när antalet parametrar som krävs för dess - approximation ökar mindre än exponentiellt med dimensionaliteten. En öppen fråga är den lämpliga definitionen av sparsamhet. Begreppet sparsamhet föreslår vi här är den effektiva r i ekvation 26. För en allmän funktion r k n ; vi kan definiera glesa funktioner för vilka r < < k n i
Ett annat relevant och insiktsfullt arbete är REF, som beaktar bredd vs. djup och ger allmänna resultat på uttrycklighet av funktioner med en kompositionsnatur.
Why and When Can Deep -- but Not Shallow -- Networks Avoid the Curse of Dimensionality: a Review
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Mathematics', 'Computer Science']}