Rademacherkomplexitet

Rademacherkomplexitet är ett mått på kapaciteten hos en klass av funktioner i maskininlärning och används främst i teorin för att ge generalisering Bounds som kopplar träningsprestanda till hur väl modellen kan generalisera till ny data. Den fungerar som ett datadrivet mått på hur väl funktioner i klassen kan fånga slumpmässigt brus utan att överanpassa.

För en given träningssats S = {x1, ..., xn} och en klass F av funktioner f: X → [0,1] definieras den empiriska Rademacherkomplexiteten som hatR_S(F) = E_sigma[ sup_{f ∈ F} (1/n) ∑_{i=1}^n sigma_i f(x_i) ], där sigma_i är oberoende Rademacher-variabler (lika sannolikhet för +1 och -1). Den förväntade Rademacherkomplexiteten är E_S[ hatR_S(F) ]. Således är hatR_S(F) ett datadrivet mått för den specifika träningssatsen, medan den förväntade versionen över alla möjliga satter ger ett modelloberoende mått.

Intuitionen är att en stor Rademacherkomplexitet indikerar att funktionsklassen kan anpassa sig till slumpmässiga störningar i data, vilket tyder på hög kapacitet och därmed potentiell överanpassning. Den används i generaliseringsteorins bounds, ofta tillsammans med Lipschitz-kontraktion och andra tekniker, för att visa att med hög sannolikhet över träningssatsen ligger den verkliga risken nära den empiricala risken upp till termer som beror på Rademacherkomplexiteten.

I praktiken uppskattar man den empiriska komplexiteten via simuleringar med olika slumpmässiga sigma-värden. För klasser med VC-dimension d är Rademacherkomplexiteten vanligtvis av storleksordningen O(√(d/n)); mer detaljerade bounds beror på specifika egenskaper hos F och den använda förlustfunktionen.