Złożoność Rademachera

W teorii uczenia się obliczeniowego ( uczenie maszynowe i teoria obliczeń ) złożoność Rademachera , nazwana na cześć Hansa Rademachera , mierzy bogactwo klasy funkcji o wartościach rzeczywistych w odniesieniu do rozkładu prawdopodobieństwa .

Definicje

Złożoność Rademachera zbioru

Biorąc pod uwagę zbiór , złożoność Rademachera A jest zdefiniowana w następujący sposób: ${\ displaystyle A \ subseteq \ mathbb {R} ^ {m}}$

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

gdzie ${\ displaystyle \ sigma _ {1}, \ sigma _ {2}, \ kropki, \ sigma _ {m}}$ są niezależnymi zmiennymi losowymi losowanymi z rozkładu Rademachera , tj. ${\ Displaystyle \ Pr (\ sigma _ {i} = +1) = \ Pr (\ sigma _ {i} = -1) = 1/2}$ za ${\ Displaystyle i = 1,2, \ kropek, m}$ i ${\ Displaystyle a = (a_ {1}, \ ldots, a_{m})}$ . Niektórzy autorzy przyjmują wartość bezwzględną sumy przed przyjęciem supremum, ale jeśli jest $symetryczne,$ nie ma to znaczenia.

Złożoność Rademachera klasy funkcji

Niech ${\ Displaystyle S = (z_ {1}, z_ {2}, \ kropki, z_ {m}) \ w Z ^ {m}}$$o$ próbką punktów i rozważ klasę funkcji $.$ wartościach rzeczywistych Następnie empiryczna złożoność Rademachera , $uwagę$ pod ${\ displaystyle S}$ definiuje się jako:

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

Można to również zapisać, korzystając z poprzedniej definicji:

${\ Displaystyle \ nazwa operatora {Rad} _ {S} (F) = \ nazwa operatora {Rad} (F \ circ S)}$

gdzie oznacza złożenie funkcji , tj. ${\ displaystyle F \ circ S}$

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

Niech $po$ rozkładem $_$ . Złożoność Rademachera klasy $F$ w odniesieniu do $}$ próbki wynosi: ${\ displaystyle$

${\ Displaystyle \ operatorname {Rad} _ {P, m} (F): = \ mathbb {E} _ {S \sim P^{m}}\left[\operatorname {Rad} _{S}(F)\right]}$

gdzie powyższe oczekiwanie jest uwzględniane w identycznie niezależnie rozłożonej próbce (iid) ${\ displaystyle S = (z_ {1}, z_ {2}, \ kropek, z_ { m})}$ wygenerowane zgodnie z ${\ displaystyle P}$ .

Intuicja

Złożoność Rademachera jest zwykle stosowana w klasie funkcji modeli używanych do klasyfikacji w celu pomiaru ich zdolności do klasyfikowania punktów wylosowanych z przestrzeni prawdopodobieństwa pod dowolnymi etykietami. Gdy klasa funkcji jest wystarczająco bogata, zawiera funkcje, które można odpowiednio dostosować do każdego układu etykiet, symulowanego przez losowe losowanie $oczekiwań ,$ aby ta ilość w sumie jest zmaksymalizowane.

Przykłady

1. $zawiera$ pojedynczy wektor, np. ${\ Displaystyle A = \ {(a, b) \} \ podzbiór \ mathbb {R} ^$ . Następnie:

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

To samo dotyczy każdej klasy hipotez singletonowych.

2. zawiera $wektory$ , np. ${\ Displaystyle A = \ {(1,1), (1,2) \}\subset \mathbb {R} ^{2}}$ . Następnie:

${\ Displaystyle {\ początek {wyrównane} \ operatorname {Rad} (A) i = {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}}}$

Korzystanie ze złożoności Rademachera

Złożoność Rademachera można wykorzystać do wyznaczenia zależnych od danych górnych granic możliwości uczenia się klas funkcji. Intuicyjnie łatwiej jest nauczyć się klasy funkcyjnej o mniejszej złożoności Rademachera.

Granice reprezentatywności

W uczeniu maszynowym $pożądany$ jest zbiór szkoleniowy reprezentujący prawdziwy rozkład niektórych przykładowych . Można to określić ilościowo, korzystając z pojęcia reprezentatywności . Oznacz przez $, z$ prawdopodobieństwa którego pobierane są próbki. Oznacz przez zbiór hipotez (potencjalne klasyfikatory) i oznacz przez $\$$displaystyle F}$$displaystyle h \ in H$ funkcji błędu, tj. dla każdej hipotezy $} cechy, etykieta) do$ funkcja , odwzorowuje każdą próbkę treningową ( $.$ klasyfikatora (uwaga w tym przypadku hipoteza i klasyfikator są używane zamiennie) Na przykład w przypadku, gdy reprezentuje klasyfikator $binarny$ , funkcja błędu jest funkcją straty 0–1, tj. funkcją $zwraca$$klasyfikuje$ , jeśli próbkę i 0 w innych przypadkach. Pomijamy indeks i piszemy $,$ gdy $podstawowa$ hipoteza jest Definiować:

${\ Displaystyle L_ {P} (f): = \ mathbb {E} _ {z \ sim P} [f (z)]}$ - oczekiwany błąd jakiejś funkcji błędu $P.$ rozkładzie $displaystyle P}$ ;

${\ Displaystyle L_ {S} (f): = {1 \ ponad m} \ suma _ {i = 1} ^ {m} f (z_ {i})} - szacowany błąd$ jakiejś funkcji błędu ${\ displaystyle f \ in F$$próbce$ na .

Reprezentatywność próbki w odniesieniu do i $definiowana$ jest jako: $S}$$displaystyle$

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

Mniejsza reprezentatywność jest lepsza, ponieważ pozwala uniknąć nadmiernego dopasowania : oznacza to, że prawdziwy błąd klasyfikatora nie jest dużo wyższy niż jego błąd szacowany, zatem wybranie klasyfikatora o niskim oszacowanym błędzie zapewni, że prawdziwy błąd będzie również Niski. Należy jednak zauważyć, że koncepcja reprezentatywności jest względna i dlatego nie można jej porównywać pomiędzy różnymi próbami.

Oczekiwaną reprezentatywność próby można ograniczyć powyżej złożoności Rademachera klasy funkcji:

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

Granica błędu uogólnienia

Gdy złożoność Rademachera jest mała, możliwe jest poznanie klasy hipotezy H poprzez empiryczną minimalizację ryzyka .

$w H}$ przykład (z binarną funkcją błędu) dla każdej $prawdopodobieństwem$ co najmniej $delta}$$displaystyle$ :

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

Granica złożoności Rademachera

Ponieważ mniejsza złożoność Rademachera jest lepsza, przydatne jest określenie górnych granic złożoności Rademachera różnych zestawów funkcji. $reguł można użyć$ górnego ograniczenia złożoności .

1. Jeśli wszystkie wektory w , $A$ Rad ( ) nie zmienia się za $m}}$ { R} ^ .

$A$ Jeśli wszystkie wektory $pomnożone$ zostaną skalar , Rad ( ) zostanie pomnożony przez ${\ displaystyle | c |}$ .

3. ${\ displaystyle \ nazwa operatora {Rad} (A + B) = \ nazwa operatora {Rad} (A) + \ nazwa operatora {Rad} ( B)}$ .

4. (Lemat Kakade i Tewari) Jeśli wszystkie wektory w $($ obsługiwane przez funkcję Lipschitza , wówczas Rad ( A ) jest co najwyżej) mnożony przez stałą Lipschitza tej funkcji. W szczególności, jeśli wszystkie wektory w $,$ obsługiwane przez mapowanie skrócenia wówczas Rad ( A ) ściśle maleje.

5. Złożoność Rademachera wypukłego $A$ równa się Rad ( ).

6. (Lemat Massarta) Złożoność Rademachera skończonego zbioru rośnie logarytmicznie wraz ze wzrostem rozmiaru zbioru. Formalnie niech $zbiorem$ wektorów $w$ i niech $}}$$N$$}$$będzie$ średnią wektorów . Następnie:

${\ Displaystyle \ operatorname {Rad} (A) \ równoważnik \ max _ {a \ w A} \ | a- {\ bar {a}}\|\cdot {{\sqrt {2\log N}} \ponad m}}$

W szczególności, jeśli jest $displaystyle A$ wektorów binarnych, normą jest co najwyżej $}$ więc: ZA {\

${\ Displaystyle \ operatorname {Rad} (A) \ równoważnik {\ sqrt {2 \ log N \ ponad m}}}$

Granice związane z wymiarem VC

Niech będzie rodziną $zbiorową$ , $_$ VC wynosi . Wiadomo, że funkcja wzrostu jest ograniczona jako: ${\ displaystyle H}$

dla wszystkich ${\ Displaystyle m> d + 1}$ : ${\ Displaystyle \ operatorname {Wzrost} (H, m) \ równoważnik (em / d)^{d}}$

$,$ że dla każdego $zawierającego$ najwyżej elementy ${\ Displaystyle | H \ czapka h | \ równoważnik (em / d) ^ {d}}$ . Rodzinę $zbiorów$ można $uznać$ za Podstawienie tego w lemacie Massarta daje:

${\ Displaystyle \ operatorname {Rad} (H \ czapka h) \ równoważnik {\ sqrt {2d \ log (em / d) \ ponad m }}}$

Za pomocą bardziej zaawansowanych technik ( granica entropii Dudleya i górna granica Hausslera) można na przykład wykazać, że istnieje stała $}}$ , że ​​dowolna klasa $displaystyle$$}$ -funkcje wskaźnikowe z $złożoność$$którego$ – Chervonenkisa, ograniczona górną granicą przez .

Granice związane z klasami liniowymi

Poniższe granice są związane $z$$operacjami$ stałym zestawie $.$ w

1. Zdefiniuj $= \ {(w \ cdot x_ {1}, \ ldots , w \ cdot x_ {m}) \ mid \| w \ | _ {2} \ równoważnik 1 \} =}$$zbiór$ iloczynów skalarnych wektorów w wektorami w kuli jednostkowej . Następnie:

${\ Displaystyle \ operatorname {Rad} (A_ {2}) \ równoważnik {\ max _ {i} \ | x_ {i} \ | _ {2} \ ponad {\ sqrt {m}}}}$

2. Zdefiniuj ${\ Displaystyle A_ {1} = \ {(w \ cdot x_ {1}, \ ldots , w \ cdot x_ {m}) \ mid \| w \ | _ {1} \ równoważnik 1 \} =}$ zbiór iloczynów skalarnych wektorów w z wektorami w kuli jednostkowej ${\ displaystyle S}$ norma 1. Następnie:

${\ Displaystyle \ operatorname {Rad} (A_ {1}) \ równoważnik \ max _ {i} \ | x_ {i }\|_{\infty }\cdot {\sqrt {2\log(2n) \ponad m}}}$

Granice związane z zakrywaniem liczb

$.$ złożoność zbioru Rademachera z jego zewnętrzną liczbą pokrycia $-$ liczbą kulek o danym $których$ , zawiera Wiązanie przypisuje się Dudleyowi.

Załóżmy, $\ displaystyle A \ podzbiór \ mathbb {R} ^ {m$ jest zbiorem wektorów, których długość (norma) wynosi co najwyżej do $}$ . Następnie dla każdej liczby całkowitej ${\ displaystyle M> 0}$ :

${\ Displaystyle \ operatorname {Rad} (A) \ równoważnik {c \ cdot 2 ^ {-M} \ ponad {\ sqrt {m}}} + {6c \ ponad m} \ cdot \ suma _ {i = 1} ^{M}2^{-i}{\sqrt {\log \left(N_{c\cdot 2^{-i}}^{\text{ext}}(A)\right)}}}$

$}$ szczególności, jeśli $\ displaystyle A$ w d -wymiarowej podprzestrzeni , to: ZA

${\ Displaystyle \ forall r> 0: N_ {r} ^ {\ tekst {ext}} (A) \ równoważnik (2c {\ sqrt {d}}/r)^{d}}$

Podstawienie tego w poprzednim wiązaniu daje następującą granicę złożoności Rademachera:

${\ Displaystyle \ nazwa operatora {Rad} (A) \ równoważnik {6c \ ponad m}\cdot {\bigg (}{\sqrt {d\log(2{\sqrt {d}})}}+2{\sqrt {d}}{\bigg )}=O{\bigg (} {c{\sqrt {d\log(d)}} \over m}{\bigg )}}$

Złożoność Gaussa

Złożoność Gaussa to podobna złożoność $ją$$uzyskać ze złożoności$ za pomocą zmiennych losowych zamiast , gdzie ${ i} \ sim {$ Gaussa i.id o średniej zerowej i wariancji 1, tj. $mathcal {N}} ( 0,1)}$ N . Wiadomo, że złożoność Gaussa i Rademachera jest równoważna aż do współczynników logarytmicznych.

Równoważność złożoności Rademachera i Gaussa

Biorąc $oznacza to,$$}$ że: $\ displaystyle {\ Frac {G (A)} {2 {\ sqrt {\ log {n}}}}} \ równoważnik {\ tekst {Rad}} (A) \ równoważnik {\ sqrt {\ Frac {\ pi} 2}}}$$A sol ( ZA ) {\ displaystyle G (A)}$ Gdzie jest złożonością gaussowską

• Peter L. Bartlett, Shahar Mendelson (2002) Złożoność Rademachera i Gaussa: granice ryzyka i wyniki strukturalne . Journal of Machine Learning Research 3 463–482
• Giorgio Gnecco, Marcello Sanguineti (2008) Granice błędów aproksymacji poprzez złożoność Rademachera . Stosowane nauki matematyczne, tom. 2, 2008, nr. 4, 153–176