Detta papper presenterar en marginal-baserad multiklass generalization bundet för neurala nätverk som skalar med sin marginal-normaliserade spektral komplexitet: deras Lipschitz konstant, vilket innebär produkten av spektral normer av viktmatriser, gånger en viss korrigeringsfaktor. Denna gräns är empiriskt undersökt för ett standard AlexNet nätverk på mnist och cifar10 dataset, med både ursprungliga och slumpmässiga etiketter, där det nära korrelerar med de observerade överskottsriskerna. Neurala nätverk beror sin häpnadsväckande framgång inte bara på deras förmåga att passa någon datauppsättning: de generaliserar också väl, vilket innebär att de ger en nära passform på osedda data. Ett klassiskt statistiskt talesätt är att modeller som kan passa för mycket kommer att generalisera dåligt; vad händer här? Låt oss navigera de många möjliga förklaringar som ges av statistisk teori. En första iakttagelse är att varje analys baserad enbart på antalet möjliga märkningar på ett ändligt träningsset - som är fallet med VC dimension - är dömd: om funktionsklassen kan passa alla möjliga etiketter (som är fallet med neurala nätverk i standardkonfigurationer (Zhang et al., 2017)), då kan denna analys inte skilja den från insamlingen av alla möjliga funktioner! (Krizjevsky et al., 2012) utbildad på cifar10, både med original och med slumpmässiga etiketter. Triangle-markerade kurvor spår överrisk över träning epoker (på en logg skala), med en "x" markerar den tidigaste epoken med noll träningsfel. Cirkelmärkta kurvor spår Lipschitz konstanter, normaliserade så att de två kurvorna för slumpmässiga etiketter uppfyller. Lipschitz konstanter nära korrelerar med överskottsrisk, och dessutom normaliserar dem med marginaler (som resulterar i den fyrkantiga kurvan) neutraliserar tillväxt över epoker. Nästa låt oss överväga skalkänsliga mått av komplexitet, såsom Rademacher komplexitet och metrisk entropi, som arbetar direkt med real-värderade funktionsklasser, och dessutom är känsliga för deras magnituder. Figur 1 ritar upp överrisken (testfelet minus träningsfelet) över träningstiderna mot en kandidatskalakänslig komplexitetsmått, nätverkets konstant Lipschitz (produkten av spektralnormerna i deras viktmatriser), och visar att de är tätt korrelerade (vilket inte är fallet för t.ex. l 2 normen av vikterna). De data som beaktas i figur 1 är standarden cifar10 dataset, både med original och med slumpmässiga etiketter, som har använts som en sundhetskontroll vid analys av neurala nätverk generalization (Zhang et al., 2017). Det finns fortfarande ett problem med att basera en komplexitet åtgärd enbart på Lipschitz konstant (även om det redan har framgångsrikt använts för att regularisera neurala nätverk (Cisse et al., 2017) ): som beskrivs i Figur 1, åtgärden växer över tiden, trots överskottet riskplatåing. Lyckligtvis finns det en standardlösning på denna fråga: att undersöka marginalerna (ett exakt mått på förtroende) för nätets resultat. Detta verktyg har använts för att studera beteendet hos 2-lagers nätverk, öka metoder, SVMs, och många andra (Bartlett, 1996; Schapire et al., 1997; Boucheron et al., 2005); för att öka, till exempel, det finns en liknande ökning av komplexitet över tid (varje utbildning iteration lägger till en svag inlärare), medan marginalgränser korrekt stanna platt eller till och med minska. Detta beteende återvinns här: som beskrivs i Figur 1, även om standardnätverk uppvisar växande Lipschitz konstanter, normalisera dessa Lipschitz konstanter med marginalen istället ger en sönderfallande kurva. Detta arbete undersöker en komplexitet mäter för neurala nätverk som är baserad på Lipschitz konstant, men normaliseras av marginalen av prediktorn. De två centrala bidragen är följande: • Teorem 1.1 nedan kommer att ge den rigorösa förklaring av den generalisering som ligger till grund för detta arbete. I motsats till tidigare arbete, detta bundet: a) skalor med Lipschitz konstant (produkt av spektral normer för viktmatriser) dividerat med marginalen; b) har inget beroende av kombinatoriska parametrar (t.ex. antal lager eller noder) utanför log faktorer; c) är multiklass (utan uttryckligt beroende av antalet klasser); d) mäter komplexitet mot ett referensnätverk (t.ex., för ResNet (He et al., 2016), referensnätverket har identitetskartor på varje lager). Bältet anges nedan, med en allmän sammanfattning av form och analys som återfinns i avsnitt 3, de fullständiga uppgifterna förvisade till bilagan. • En empirisk undersökning, i avsnitt 2, av neurala nätverk generalisering på standarddatauppsättningarna cifar10, cifar100, och mnist med hjälp av föregående bundna. I stället för att använda den bundna för att ge ett enda nummer, kan det användas för att bilda en marginalfördelning som i figur 2. Dessa marginalfördelningar kommer att belysa följande intuitiva observationer: a) cifar10 är svårare än mnist; b) slumpmässiga etiketter gör cifar10 och mnist mycket svårare; c) marginalfördelningarna (och gränserna) konvergerar under träningen, även om viktmatriserna fortsätter att växa; d) l 2 legalisering ("viktfall") påverkar inte signifikant marginaler eller generalisering. En mer detaljerad beskrivning av marginalfördelningarna är följande. Antag att ett neuralt nätverk beräknar en funktion f : där k är antalet klasser; det mest naturliga sättet att konvertera detta till en klassificering är att välja utdatakoordinaten med den största magnituden, vilket betyder x → arg max j f (x) j. Marginalen är alltså att mäta skillnaden mellan produktionen för den korrekta etiketten och andra etiketter, vilket betyder Tyvärr verkar marginalerna i sig inte säga så mycket; se till exempel figur 2a, där samlingarna av alla marginaler för alla datapunkter - den onormaliserade marginalfördelningen - är lika för cifar10 med och utan slumpmässiga etiketter. Vad som saknas är en lämplig normalisering, som i figur 2b. Denna normalisering tillhandahålls av Theorem 1.1, som nu kan förklaras i detalj. För att ange det bundna är det nödvändigt med lite notation. Nätverken kommer att använda L fast icke-linjäritet (σ 1,. ., σ L ), där σ i är ρ i -Lipschitz (t.ex., som med koordinat-wise ReLU, och max-pooling, som diskuteras i tillägg A.1); ibland kommer det också hålla att låta F A betecknar den funktion som beräknas av motsvarande nätverk: När data (x 1,. .., x n ) ges, samla in dem som rader av en matris X  på R n×d. Ibland, notation kommer att överbelastas för att diskutera F A (X T ), en matris vars i th kolumnen är F A (x i ). Den l 2 norm · 2 är alltid beräknas ingångs-wise; alltså, för en matris, motsvarar den Frobenius normen. Nästa, definiera en samling referensmatriser (M 1,. ., M L) med varje dimension som mest W ; till exempel för att få en bra gräns för ResNet (He et al., 2016), Det är förnuftigt att ställa M i := Jag, identitetskartan, och den bundna nedan kommer att förvärras när nätverket rör sig längre från identitetskartan; för AlexNet (Krizjevsky et al., 2012), det enkla valet M i = 0 räcker. Slutligen, uthyrning · σ och · 1 betecknar spektral norm och den ovalsade l 1 vektornorm, spektral komplexitet R F A = R A i ett nätverk F A med vikter A är (1.1) Följande teorem ger en generalisering bundet för neurala nätverk vars icke-linjäritet är fast men vars vikt matriser A har avgränsat spektral komplexitet R A. Theorem 1.1. Låt icke-linjäritet (σ 1,. .., σ L ) och referensmatriser (M 1,................................ ) och referensmatriser (M 1............................................................... ., M L ) anges enligt ovan (dvs. σ i är ρ i -Lipschitz och σ i (0) = 0). Sedan med sannolikhet minst 1 − δ över en iid dragning av n exempel ((x i, y i )) n i=1, varje marginal γ > 0 och nätverk där 2. Det fullständiga beviset (baserat på metrisk entropi) förvisas till tillägget, men en skiss ges i avsnitt 3, tillsammans med en mer allmän form (inte begränsad till spektralnormer), tillsammans med en (icke-matchning!) Nedre gränsen. Avsnitt 3 ger också en diskussion om relaterat arbete, men kort sagt är det viktigt att notera att marginal och Lipschitz-känsliga gränser har en lång historia i neurala nätverk litteratur (Bartlett, 1996; Anthony och Bartlett, 1999; Neyshabur et al., 2015); distinktionen här är känsligheten för specifikt den spektral norm, liksom inget uttryckligt utseende av kombinatoriska mängder såsom antal parametrar eller lager (utanför log termer, och index för summeringar och produkter). Figur 3a, men identiska i de andra subplot; cifar10 (blå) och slumpmässiga cifar10 (gröna) fördelningar är samma varje gång. Detta avsnitt kommer nu att använda kärnan generalisering bundet, som anges i Theorem 1.1, att empiriskt studera generalisering beteende neurala nätverk via marginalfördelningar. Innan du fortsätter med tomterna, är det ett bra tillfälle att ge en mer förfinad beskrivning av marginalfördelningen, en som är lämplig för jämförelser mellan datauppsättningar. Eftersom n datapunkter ((x i, y i )) n i=1 som rader av matris X  på R n×d och prediktor F A : R d → R k med spektral komplexitet R A (jfr. ekv. (1.1)) är den (normaliserade) marginalfördelningen den unika empiriska fördelningen av datapunkterna var och en omvandlad till en enda skalar beroende på var spektral komplexiteten R A kommer från ekv. (1.1) Detta beslut riktar sig till medlemsstaterna. Normaliseringen härleds alltså från gränsen i Theorem 1.1, men ignorerar logtermer. På så sätt kan de två marginalfördelningarna för två datauppsättningar tolkas på följande sätt. Med tanke på varje fast punkt på den horisontella axeln, om den kumulativa fördelningen av den ena densiteten är lägre än den andra, motsvarar den en lägre högersida i Theorem 1.1. Av ingen annan anledning än visuell tolkning kommer tomterna här istället att avbilda en densitetsberäkning av marginalfördelningen. De vertikala och horisontella axlarna är omskalade i olika tomter, men de slumpmässiga och verkliga CIFar10 marginalfördelningarna är alltid desamma. Lite mer detaljer om den experimentella installationen är som följer. Alla experiment genomfördes i Keras (Chollet et al., 2015). För att minimera konflaterande effekter av optimering och regularisering var optimeringsmetoden vaniljsgd med stegstorlek 0,01, och all regularisering (vikt sönderfall, batch normalisering, etc.) var funktionshindrade. "cifar" i allmänhet avser cifar10, men cifar100 kommer också att vara 4 10 epoker 20 epoker 40 epoker 80 epoker 160 epoker Jämför datauppsättningar. En första jämförelse är cifar10 och standardsiffrorna för mnist. Mnist anses vara "lätt", med vilket det vanligtvis är tänkt att någon av en mängd olika metoder kan uppnå ungefär 1% testfel. "Ensamheten" bekräftas av figur 3a, där marginalfördelningen för mnist placerar all sin massa långt till höger om massan för cifar10. Intressant, slumpmässig märkning av mnist, som i figur 3b, resulterar i en marginalfördelning till vänster om inte bara cifar10, men också något till vänster om (men nära) cifar10 med randomiserade etiketter. Därefter jämför figur 3c cifar10 och cifar100, där cifar100 använder samma indatabilder som cifar10; faktum är att cifar10 erhålls från cifar100 genom att de ursprungliga 100 kategorierna slås samman till 10 grupper. Det är intressant att lägga märke till att cifar100, ur marginalgränsens perspektiv, är lika svårt som cifar10 med slumpmässiga etiketter. Detta överensstämmer med det stora test som observerats fel på cifar100 (som inte har "optimerats" på något sätt via legalisering). Slutligen ersätter figur 3d indataavbildningarna cifar10 med slumpmässiga bilder tagna från Gaussians som matchar första och andra ordningens bildstatistik (se Zhang et al., 2017) för liknande experiment). Konvergens av marginaler. Som påpekades i Avsnitt 1, vikterna i de neurala nätverken verkar inte konvergera i vanlig mening under träning (normerna växer kontinuerligt). Emellertid, som avbildas i Figur 4a, sekvensen av (normaliserad!) Marginalfördelningen är i sig konvergerande. Regularisering. Som påpekades i (Zhang et al., 2017), legalisering verkar bara medföra mindre fördelar för att testa fel (även om lämpliga att användas i alla banbrytande resultat). Denna observation överensstämmer med marginalfördelningarna i figur 4b, som inte förbättras (t.ex. genom att flytta till höger) på något synligt sätt under legalisering. En öppen fråga, som diskuteras vidare i avsnitt 4, är att utforma legalisering som förbättrar marginalerna. Detta avsnitt kommer att skissa beviset för Theorem 1.1, ange några generaliseringar, ge en lägre gräns, och diskutera relaterade arbete.  ; Observera att R γ respektive R γ är övre gränsen för sannolikheten för och andelen fel i källfördelnings- och utbildningssetet. Slutligen, med tanke på en uppsättning av verkliga-värderade funktioner H, definiera Rademacher komplexitet som R(H) := E sup h och H n i=1 i h(x i, y i ) där förväntan är över Rademacher slumpmässiga variabler Med denna notation på plats, är den grundläggande gränsen som följer. Det här är Lemma 3.1. Givna funktioner F med F f : R d → R k och alla γ > 0, definiera Därefter, med sannolikhet minst 1 − δ över ett prov S i storlek n, varje f  på F uppfyller Denna gräns är en direkt följd av standardverktyg i Rademacher komplexitet. För att omedelbart få detta bundet, kommer att täcka nummer att användas för att direkt övre gräns Rademacher komplexitet term R((F γ )  och S ). Det är intressant att lägga märke till att valet att direkt arbeta när det gäller att täcka antalet verkar vara nödvändigt för att ge ett band utan uttryckligt beroende av k; däremot, tidigare arbete främst (solely?) hanterar multiclass via en Rademacher komplexitetsanalys på varje koordinat av en k-tuple av funktioner, och betalar en faktor ε k (Zhang, 2004). Detta underavsnitt bevisar Theorem 1.1 via Lemma 3.1 genom att kontrollera Rademacher komplexitet R((F γ )  på nätverk med begränsad spektral komplexitet genom att täcka nummer. Detta första steg är att bevisa en mer allmän täckning antal bundna (i termer av allmänna operatörsnormer) som så småningom kommer att specialiseras på l 2 data normer och spektral operatör normer för att bevisa Theorem 1.1. En lockande riktning för framtida arbete är att specialisera den allmänna bundna på andra sätt, nämligen de som är bättre anpassade till geometrin i neurala nätverk som påträffas i praktiken. Nätverkens struktur är densamma som tidigare, nämligen med tanke på matriser med konventionen F ∅ (Z) = Z. • Inmatningen Z  på V 1 är associerad med vissa norm  med 1 ≤ B. Subskriptet anger endast ett index, och hänvisar inte till någon l 1 norm. Vektorutrymmet V 1, Och dessutom den slutliga samlingen av vektorutrymmen (V 1,. .., V L ), har ingen fast mening och är helt enkelt abstrakt vektor utrymmen. Men när du använder dessa verktyg för att bevisa Theorem 1.1, V 1 = R d×n och Z  på V 1 bildas genom att samla n datapunkter i sina kolumner; det vill säga Z = X. • De linjära operatörerna A i : V i → W i+1 är associerade med någon operatör norm  och A i i→i+1 ≤ c i : där än en gång är i+1 en abstrakt norm som införs enbart för att ge detta bevis mer flexibilitet. Som tidigare nämnts, dessa linjära operatörer A = (A 1,. .., A L ) varierar mellan funktioner F A. När används för att bevisa Theorem 1.1, Z är en matris (den främre bilden av datamatris X över lager), och dessa normer är alla matris normer. • De ρ i -Lipschitz kartläggningar σ i : W i+1 → V i+1 har ρ i mätt med avseende på normer. ·  på i+1 och  för i+1 : för alla z, z  på W i+1, Dessa Lipschitz kartläggningar anses fasta inom F A. Observera återigen att dessa åtgärder, när de tillämpas för att bevisa Theorem 1.1, fungerar på matriser som representerar framåtbilder av alla datapunkter tillsammans. Lipschitz egenskaper hos standardkoordinatmässigt ReLU och maxpooling operatörer finns i tillägg A.1. Slutligen, strax innan gränsen anges, är notationen för (riktig) täckning nummer som följer. Den notation N (U,, · ) innebär den minsta kardinalitet av någon delmängd V  till U som täcker U på skalan med norm ·, vilket betyder sup A-U min B-V
En annan tråd av arbete REF Neyshabur et al., 2017b,a) försöker utveckla nya komplexitetsåtgärder som kan karakterisera generaliseringens prestanda i praktiken.
Spectrally-normalized margin bounds for neural networks
{'venue': 'ArXiv', 'journal': 'ArXiv', 'mag_field_of_study': ['Computer Science', 'Mathematics']}