Rademacher komplexitet

I beräkningslärandeteori ( maskininlärning och beräkningsteori ) mäter Rademachers komplexitet , uppkallad efter Hans Rademacher , rikedomen hos en klass av verkligt värderade funktioner med avseende på en sannolikhetsfördelning .

Definitioner

Rademacher komplexitet av en uppsättning

Givet en mängd $A\subseteq \mathbb {R} ^{m}$ definieras Rademacher- komplexiteten för A enligt följande:

$\operatorname {Rad} (A):={\frac {1}{m}}\ mathbb {E} _{\sigma }\left[\sup _{a\in A}\sum _{i=1}^{m}\sigma _{i}a_{i}\right]$

där $\sigma _{1},\sigma _{2},\dots ,\sigma _{m}$ är oberoende slumpvariabler hämtade från Rademacher-fördelningen dvs ${\displaystyle \Pr(\sigma _{i}=+1)=\Pr(\sigma _{i}=-1$ för $i=1,2,\dots ,m$ och $a=(a_{1 },\ldots ,a_{m})$ . Vissa författare tar det absoluta värdet av summan innan de tar det högsta, men om $A$ är symmetrisk gör det ingen skillnad.

Rademacher komplexitet för en funktionsklass

Låt $S=(z_{1},z_{2},\dots ,z_{m})\in Z^{m}$ vara ett exempel på punkter och betrakta en funktionsklass ${\mathcal {F}}$ av verkliga funktioner över $Z^{m}$ . Sedan definieras den empiriska Rademacher-komplexiteten för ${\mathcal {F}}$ givet ${\displaystyle S} som:$

$\operatorname {Rad} _{S}({\mathcal {F}}) ={\frac {1}{m}}\mathbb {E} _{\sigma }\left[\sup _{f\in {\mathcal {F}}}\sum _{i=1}^{m }\sigma _{i}f(z_{i})\right]$

Detta kan också skrivas med den tidigare definitionen:

$\operatörsnamn {Rad} _{S}(F)=\operatörsnamn {Rad} (F\circ S)$

där $F\circ S$ anger funktionssammansättning , dvs.

$F\circ S:=\{(f(z_{1}),\ldots ,f (z_{m}))\midt f\in F\}$

Låt $P$ vara en sannolikhetsfördelning över $Z$ . Rademacher- komplexiteten för funktionsklassen $F$ med avseende på $P$ för provstorlek $m$ är:

$\operatörsnamn {Rad} _{P,m}(F):=\mathbb {E} _{S \sim P^{m}}\vänster[\operatörsnamn {Rad} _{S}(F)\höger]$

där ovanstående förväntan tas över ett identiskt oberoende fördelat (iid) sampel $S=(z_{1},z_{2},\dots ,z_{ m})$ genererad enligt $P$ .

Intuition

Rademacher-komplexiteten appliceras vanligtvis på en funktionsklass av modeller som används för klassificering, med målet att mäta deras förmåga att klassificera punkter dragna från ett sannolikhetsutrymme under godtyckliga märkningar. När funktionsklassen är tillräckligt rik innehåller den funktioner som på lämpligt sätt kan anpassas för varje arrangemang av etiketter, simulerade av slumpmässig dragning av $\sigma _{i}$ under förväntan, så att denna kvantitet i summan är maximerad.

Exempel

1. $A$ innehåller en enkel vektor, t.ex. $A=\{(a,b)\}\subset \mathbb {R} ^{ 2}$ . Sedan:

${ \displaystyle \operatorname {Rad} (A)={1 \over 2}\cdot \left({1 \over 4}\cdot (a+b)+{1 \over 4}\cdot (ab)+{1 \over 4}\cdot (-a+b)+{1 \over 4}\cdot (-ab)\right)=0}$

Detsamma gäller för varje singelhypotesklass.

2. $A$ innehåller två vektorer, t.ex. $A=\{(1,1),(1,2) \}\subset \mathbb {R} ^{2}$ . Sedan:

${\begin{aligned}\operatörsnamn {Rad} (A )&={1 \over 2}\cdot \left({1 \over 4}\cdot \max(1+1,1+2)+{1 \over 4}\cdot \max(1-1,1 -2)+{1 \over 4}\cdot \max(-1+1,-1+2)+{1 \over 4}\cdot \max(-1-1,-1-2)\right) \\[5pt]&={1 \over 8}(3+0+1-2)={1 \over 4}\end{aligned}}$

Använder Rademacher-komplexiteten

Rademacher-komplexiteten kan användas för att härleda databeroende övre gränser för funktionsklassers inlärbarhet . Intuitivt är en funktionsklass med mindre Rademacher-komplexitet lättare att lära sig.

Begränsa representativiteten

I maskininlärning är det önskvärt att ha en träningsuppsättning som representerar den sanna fördelningen av vissa exempeldata $S$ . Detta kan kvantifieras med hjälp av begreppet representativitet . Beteckna med $P$ sannolikhetsfördelningen från vilken stickproven dras . Beteckna med $H$ uppsättningen hypoteser (potentiella klassificerare) och beteckna med $F$ motsvarande uppsättning felfunktioner, dvs. för varje hypotes $h\in H$ , där är en funktion $f_{h}\in F$ , som mappar varje träningsprov (funktioner, etikett) till felet för klassificeraren $h$ (observera att hypotes och klassificerare i detta fall är används omväxlande). Till exempel, i det fall $h$ representerar en binär klassificerare, är felfunktionen en 0–1 förlustfunktion, dvs felfunktionen $f_{h}$ returnerar 1 om $h$ klassificerar korrekt ett prov och 0 annat. Vi utelämnar indexet och skriver $f$ istället för $f_{h}$ när den underliggande hypotesen är irrelevant. Definiera:

${\displaystyle L_{P}(f):=\mathbb {E} _{z\sim P}[f(z)]} –$ den förväntat fel för någon felfunktion $f\in F$ på den verkliga fördelningen $P$ ;

$L_{S}(f):={1 \over m}\summa _{i=1}^{m}f (z_{i})$ – det uppskattade felet för någon felfunktion $f\in F$ på provet $S$ .

Representativiteten för provet $S$ , med avseende på $P$ och $F$ , definieras som:

$\operatorname {Rep} _{P}(F,S):=\sup _{ f\in F}(L_{P}(f)-L_{S}(f))$

Mindre representativitet är bättre, eftersom det ger ett sätt att undvika överanpassning : det betyder att det sanna felet för en klassificerare inte är mycket högre än dess uppskattade fel, och så att välja en klassificerare som har lågt uppskattat fel kommer att säkerställa att det sanna felet också är låg. Observera dock att begreppet representativitet är relativt och därför inte kan jämföras mellan olika urval.

Den förväntade representativiteten för ett urval kan ovan avgränsas av Rademacher-komplexiteten för funktionsklassen:

$$\mathbb {E} _{S\sim P^{m} }[\operatörsnamn {Rep} _{P}(F,S)]\leq 2\cdot \mathbb {E} _{S\sim P^{m}}[\operatörsnamn {Rad} (F\circ S) ]$$

Avgränsning av generaliseringsfelet

När Rademacher-komplexiteten är liten är det möjligt att lära sig hypotesklassen H med hjälp av empirisk riskminimering .

Till exempel, (med binär felfunktion), för varje $\delta >0$ , med sannolikhet minst $1-\delta$ , för varje hypotes $h\ i H$ :

$L_{P}(h)-L_{S}(h)\ leq 2\operatörsnamn {Rad} (F\circ S)+4{\sqrt {2\ln(4/\delta ) \over m}}$

Begränsar Rademacher-komplexiteten

Eftersom mindre Rademacher-komplexitet är bättre är det användbart att ha övre gränser för Rademacher-komplexiteten för olika funktionsuppsättningar. Följande regler kan användas för att övergränsa Rademacher-komplexiteten för en mängd $A\subset \mathbb {R} ^{m}$ .

1. Om alla vektorer i $A$ översätts med en konstant vektor ${\displaystyle a_{0}\in \mathbb {R} ^{m}} så$ ändras inte Rad( A ) .

2. Om alla vektorer i $A$ multipliceras med en skalär ${\displaystyle c\in \mathbb {R} } , så$ multipliceras Rad( A ) med $|c|$ .

3. $\operatörsnamn {Rad} (A+B)=\operatörsnamn {Rad} (A)+\operatörsnamn {Rad} ( B)$ .

4. (Kakade & Tewari Lemma) Om alla vektorer i $A$ drivs av en Lipschitz-funktion , så multipliceras Rad( A ) (högst) med Lipschitz-konstanten för funktionen. I synnerhet, om alla vektorer i $A$ drivs av en sammandragningsmappning , så minskar Rad( A ) strikt.

5. Rademacher-komplexiteten för det konvexa skrovet av $A$ är lika med Rad( A ).

6. (Massart Lemma) Rademacher-komplexiteten hos en finit mängd växer logaritmiskt med mängdens storlek. Formellt, låt $A$ vara en uppsättning av $N$ vektorer i $\mathbb {R} ^{m}$ och låt ${\bar {a} }$ vara medelvärdet av vektorerna i $A$ . Sedan:

$\operatorname {Rad} (A)\leq \max _{a\in A}\|a-{\ stapel {a}}\|\cdot {{\sqrt {2\log N}} \over m}$

I synnerhet, om $A$ är en uppsättning binära vektorer, är normen högst ${\sqrt {m}}$ , så:

$\operatorname {Rad} (A)\leq {\sqrt {2\log N \over m}}$

Gränser relaterade till VC-dimensionen

Låt $H$ vara en uppsättningsfamilj vars VC-dimension är $d$ . Det är känt att tillväxtfunktionen för $H$ är begränsad som:

för alla $m>d+1$ : $\operatorname {Tillväxt} (H,m)\leq (em/ d)^{d}$

Detta betyder att för varje uppsättning $h$ med högst $m$ element, $|H\cap h|\leq (em/d)^{d}$ . Uppsättningsfamiljen $H\cap h$ kan betraktas som en uppsättning binära vektorer över $\mathbb {R} ^{m}$ . Att ersätta detta i Massarts lemma ger:

$\operatorname {Rad} (H\cap h)\leq {\sqrt {2d\log(em/d) \over m }}$

Med mer avancerade tekniker ( Dudleys entropigräns och Hausslers övre gräns) kan man till exempel visa att det finns en konstant ${\displaystyle C} ,$ så att vilken klass som helst av $\{0,1\ }$ -indikatorfunktioner med Vapnik–Chervonenkis dimension $d$ har Rademacher-komplexitet som är övre gränsen till $C{\sqrt {\frac {d}{m}}}$ .

Gränser relaterade till linjära klasser

Följande gränser är relaterade till linjära operationer på $S$ – en konstant uppsättning $m$ vektorer i $\mathbb {R} ^{n}$ .

1. Definiera $A_{2}=\{(w\cdot x_{1},\ldots ,w\cdot x_{m})\mid \|w\|_{2}\leq 1\}=$ uppsättningen punktprodukter av vektorerna i $S$ med vektorer i enhetskulan . Sedan:

$\operatörsnamn {Rad} (A_{2})\leq {\max _{i}\|x_{i}\|_{2} \over {\sqrt {m}}}$

2. Definiera $A_{1}=\{(w\cdot x_{1},\ldots ,w\cdot x_{m})\mid \|w\|_{1}\leq 1\}=$ uppsättningen punktprodukter av vektorerna i $S$ med vektorer i enhetsbollen för 1-normen. Sedan:

$\operatorname {Rad} (A_{1})\leq \max _{i}\|x_{i }\|_{\infty }\cdot {\sqrt {2\log(2n) \over m}}$

Gränser relaterade till täckande siffror

Följande gräns relaterar Rademacher-komplexiteten för en mängd $A$ till dess yttre täckningsnummer – antalet bollar med en given radie $r$ vars förening innehåller $A$ . Bindningen tillskrivs Dudley.

Antag att $A\subset \mathbb {R} ^{m}$ är en uppsättning vektorer vars längd (norm) som mest är $​​{\displaystyle c}$ . Sedan, för varje heltal $M>0$ :

$\operatörsnamn {Rad} (A) \leq {c\cdot 2^{-M} \over {\sqrt {m}}}+{6c \over m}\cdot \sum _{i=1}^{M}2^{-i}{ \sqrt {\log \left(N_{c\cdot 2^{-i}}^{\text{ext}}(A)\höger)}}$

I synnerhet, om $A$ ligger i ett d -dimensionellt delrum av $\mathbb {R} ^{m}$ , då:

$\forall r>0:N_{r}^{\text{ext}}(A)\leq (2c{\sqrt {d}}/r)^{d}$

Att ersätta detta i den föregående gränsen ger följande gräns för Rademacher-komplexiteten:

$\operatörsnamn {Rad} (A)\leq {6c \ över m}\cdot {\bigg (}{\sqrt {d\log(2{\sqrt {d}})}}+2{\sqrt {d}}{\bigg )}=O{\bigg (} {c{\sqrt {d\log(d)}} \over m}{\bigg )}$

Gaussisk komplexitet

Gaussisk komplexitet är en liknande komplexitet med liknande fysiska betydelser, och kan erhållas från Rademacher-komplexiteten genom att använda de slumpmässiga variablerna $g_{i}$ istället för $\sigma _{i}$ , där $g_{i}$ är gaussiska i.id slumpvariabler med nollmedelvärde och varians 1, dvs $g_{i}\sim {\mathcal {N}}( 0,1)$ . Gaussiska och Rademacher komplexitet är kända för att vara ekvivalenta upp till logaritmiska faktorer.

Likvärdighet mellan Rademacher och Gaussisk komplexitet

Givet en mängd $A\subseteq \mathbb {R} ^{n}$ så gäller det att: ${\ displaystyle {\frac {G(A)}{2{\sqrt {\log {n}}}}}\leq {\text{Rad}}(A)\leq {\sqrt {\frac {\pi }{ 2}}}G(A)}$ Där $G(A)$ är den Gaussiska komplexiteten för A

• Peter L. Bartlett, Shahar Mendelson (2002) Rademacher och Gaussiska komplexiteter: riskgränser och strukturella resultat . Journal of Machine Learning Research 3 463–482
• Giorgio Gnecco, Marcello Sanguineti (2008) Approximationsfelgränser via Rademachers komplexitet . Applied Mathematical Sciences, Vol. 2, 2008, nr. 4, 153-176