Przykładowa złożoność

Złożoność próbki algorytmu uczenia maszynowego reprezentuje liczbę próbek szkoleniowych potrzebnych do pomyślnego nauczenia się funkcji docelowej.

Mówiąc dokładniej, złożoność próbki to liczba próbek uczących, które musimy dostarczyć algorytmowi, aby funkcja zwrócona przez algorytm mieściła się w granicach dowolnie małego błędu najlepszej możliwej funkcji, z prawdopodobieństwem dowolnie bliskim 1.

Istnieją dwa warianty złożoności próbki:

• Słaby wariant naprawia określony rozkład wejścia-wyjścia;
• Wariant silny przyjmuje złożoność próbki w najgorszym przypadku dla wszystkich rozkładów wejścia-wyjścia.

twierdzenie o braku wolnego obiadu dowodzi, że generalnie złożoność próby silnej jest nieskończona, tj. że nie ma algorytmu, który mógłby nauczyć się globalnie optymalnej funkcji celu przy użyciu skończonej liczby próbek uczących.

Jeśli jednak interesuje nas tylko określona klasa funkcji docelowych (np. tylko funkcje liniowe), to złożoność próbki jest skończona i zależy liniowo od wymiaru VC klasy funkcji docelowych.

Definicja

Niech $displaystyle X}$$\$$} styl wyświetlania X\razy Y}$ przestrzenią, którą nazywamy przestrzenią wejściową, i przestrzenią, którą nazywamy przestrzenią wyjściową, i niech oznacza iloczyn ${\$ . Na przykład przy ustawieniu klasyfikacji binarnej to zazwyczaj skończenie wymiarowa przestrzeń wektorowa, a ${\ displaystyle Y}$$to$ zbiór ${\ Displaystyle \ {-1,1 \}}$ .

Napraw hipotezę przestrzeni funkcji $\$$displaystyle h \ okrężnica X \ do Y$ . Algorytm uczenia się przez to obliczalna mapa od ${\ displaystyle {\ mathcal {H}}$$}$ do $}}$ . Innymi słowy, jest to algorytm, który pobiera jako dane wejściowe skończoną sekwencję próbek treningowych i wyprowadza funkcję od do ${\ displaystyle X}$${\ Displaystyle Y}$ . Typowe algorytmy uczenia obejmują empiryczną minimalizację ryzyka , bez lub z regularyzacją Tichonowa .

Napraw funkcję straty ${\ Displaystyle {\ mathcal {L}} \ dwukropek Y \ razy Y \ do \ mathbb {R} _ {\ geq 0}}, na przykład$ strata kwadratowa ${\ Displaystyle {\ mathcal {L}} (y, y ') = (yy') ^ {2}}$ , gdzie ${ \displaystyle h(x)=y'}$ . $}$ danego rozkładu na oczekiwane ryzyko hipotezy (funkcji) $\ Displaystyle \ rho}$ na $razy$${\ Displaystyle X \$ jest

${\ Displaystyle {\ mathcal {E}} (h):=\mathbb {E} _{\rho }[{\mathcal {L}}(h(x),y)]=\int _{X\times Y}{\mathcal {L}}( h(x),y)\,d\rho (x,y)}$

$_$$_$ mamy gdzie algorytmem i ${\ Displaystyle S_ {n} = ((x_ {1}, y_ {1}), \ ldots, (x_ {n}, y_ {n}}) \ sim \ rho ^ {n}} to ciąg$ wektorów które wszystkie są rysowane niezależnie od ${\ displaystyle \ rho}$ . Zdefiniuj optymalne ryzyko

$${\ Displaystyle {\ mathcal {E}} _ {\ mathcal {H}} ^ {*} = {\ underset {h \ in {\ mathcal {H}}} {\ inf}} {\ mathcal {E}} (H).}$$

Ustaw ${\ Displaystyle h_ {n} = {\ mathcal {A}} (S_ {n})}$ dla każdego ${\ displaystyle n}$ . Zauważ, że $} }$$zależy$ i zmiennej losowej , która jest losowana z rozkładu $Displaystyle \ rho ^ {$ n . Algorytm $wywoływany$ _ mi ${\ Displaystyle {\ mathcal {E}} (h_ {n})}$${\ mathcal {E}} _ {\ mathcal {H}} ^ { *}}$ zbiega się mi Displaystyle . Innymi słowy, dla wszystkich $taka$$n \ geq N}$ całkowita , że ​​dla wszystkich $\$ , mamy

$${\ Displaystyle \ Pr _ {\ rho ^ {n}} [{\ mathcal {E}} (h_ {n}) - {\ mathcal {E}} _ {\ mathcal {H}} ^ {*} \ geq \varepsilon ]<\delta .}$$

Złożoność próbki jest wtedy minimum , dla którego to zachodzi, ${\ Displaystyle \ delta}$ funkcja i $δ$$ρ$$}$ \ epsilon . Piszemy złożoność próbki jako ${\ Displaystyle N (\ rho, \ epsilon, \ delta)}$ , aby podkreślić, że ta wartość ${\ Displaystyle N}$ zależy od ${\ Displaystyle \ rho, \ epsilon}$ i ${\ Displaystyle \ delta}$ . Jeśli nie jest $spójne$ , to ustawiamy $\ rho, \ epsilon, \ delta) = \ infty}$ . Jeśli istnieje algorytm, dla którego $,$$\ epsilon, \ delta)}$ jest skończony, to mówimy, że przestrzeń hipotezy możliwa do nauczenia .

Innymi słowy, złożoność próbki ${$ algorytmu: biorąc pod uwagę pożądaną $epsilon$ i pewności $należy$ pobrać próbki punktów danych, aby zagwarantować, że ryzyko funkcji wyjściowej mieści się w granicach ${\ Displaystyle N (\ rho, \ epsilon, \ delta)}$${\ Displaystyle \ epsilon}$ najlepszego z możliwych, z prawdopodobieństwem co najmniej ${\ Displaystyle 1-\ delta}$ .

Przy prawdopodobnie w przybliżeniu poprawnym (PAC) uczeniu się , należy się zastanowić, czy złożoność próbki jest wielomianem , to znaczy, czy jest ograniczona przez ${\ Displaystyle N (\ rho, \ epsilon, \ delta)}$ wielomian w ${\ Displaystyle 1/\ epsilon}$ i ${\ Displaystyle 1/\ delta}$ . Jeśli ${\ Displaystyle N (\ rho, \ epsilon, \ delta)}$$jest$ wielomianem dla jakiegoś algorytmu uczenia się, wtedy mówi się, że przestrzeń hipotezy możliwa do nauczenia się przez PAC . Zauważ, że jest to silniejsze pojęcie niż umiejętność uczenia się.

Nieograniczona przestrzeń hipotez: nieskończona złożoność próbki

Można zapytać, czy istnieje algorytm uczący się, dzięki któremu złożoność próbki jest skończona w silnym sensie, to znaczy istnieje ograniczenie liczby potrzebnych próbek, aby algorytm mógł nauczyć się dowolnego rozkładu w przestrzeni wejścia-wyjścia z określony błąd docelowy. Bardziej formalnie, pyta się, ${\ displaystyle$ istnieje algorytm uczenia się, ${\ mathcal {A}}}$ że dla wszystkich dodatnia liczba całkowita ${\ displaystyle N}$ takie, że dla wszystkich ${\ displaystyle n \ geq N}$ mamy

$${\ Displaystyle \ sup _ {\ rho} \ lewo (\ Pr _ {\ rho ^ {n}} [{\ mathcal {E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right)<\delta ,}$$

gdzie ${\ Displaystyle h_ {n} = {\ mathcal {A}} (S_ {n})}$ z ${\ Displaystyle S_ {n} = ((x_ {1}, y_ {1}), \ ldots, (x_ {n}, y_ {n}}) \ sim \ rho ^$ jak wyżej. Twierdzenie o braku darmowego obiadu mówi, że bez ograniczeń dotyczących przestrzeni hipotez $.$ nie jest, tj. Zawsze istnieją „złe” rozkłady, dla których złożoność próbki jest dowolnie duża

Tak więc, aby sformułować stwierdzenia dotyczące szybkości zbieżności ilości

$${\ Displaystyle \ sup _ {\ rho} \ lewo (\ Pr _ {\ rho ^ {n}} [{\ mathcal { E}}(h_{n})-{\mathcal {E}}_{\mathcal {H}}^{*}\geq \varepsilon ]\right),}$$

trzeba albo

• ograniczyć przestrzeń rozkładów prawdopodobieństwa , np. poprzez podejście parametryczne lub ${\ displaystyle \ rho}$
• ograniczyć przestrzeń hipotez $.$ jak w podejściach bez dystrybucji

Ograniczona przestrzeń hipotez: skończona złożoność próbki

$,$ takich jak wymiar VC i złożoność Rademachera , które kontrolują złożoność przestrzeni . Mniejsza przestrzeń hipotezy wprowadza większe obciążenie do procesu wnioskowania, co oznacza, że ${\ Displaystyle {\ mathcal {E}} _ {\ mathcal {H}} ^ {*}}$ może być większe niż najlepsze możliwe ryzyko na większej przestrzeni. Jednak poprzez ograniczenie złożoności przestrzeni hipotez algorytm staje się możliwy do tworzenia bardziej jednorodnie spójnych funkcji. Ten kompromis prowadzi do koncepcji regularyzacji .

Jest to twierdzenie z teorii VC , że następujące trzy stwierdzenia są równoważne dla przestrzeni hipotez: ${\ displaystyle {\ mathcal {H}}}$ :

1. ${\ displaystyle {\ mathcal {H}}}$ można nauczyć się PAC.
2. Wymiar VC $skończony$ .
3. ${\ Displaystyle {\ mathcal {H}}}$ jest jednolitą klasą Glivenko-Cantelli .

Daje to sposób na udowodnienie, że pewne przestrzenie hipotez są PAC do nauczenia, a co za tym idzie, do nauczenia.

Przykład przestrzeni hipotez możliwej do nauczenia się przez PAC

${\ Displaystyle X = \ mathbb {R} ^ {d}, Y = \ {- 1,1 \}}$ i niech ${\ Displaystyle {\ mathcal { H}}}$ będzie przestrzenią funkcji afinicznych na , czyli funkcjami postaci $b$${\ Displaystyle x \ mapsto \ langle w, x \ rangle +$ dla pewnego ${\ Displaystyle w \ w \ mathbb {R} ^ {d}, b \ w \ mathbb {R}$ . Jest to klasyfikacja liniowa z problemem uczenia się z przesunięciem. Teraz zauważ, że cztery współpłaszczyznowe punkty w kwadracie nie mogą zostać rozbite przez żadną funkcję afiniczną, ponieważ żadna funkcja afiniczna nie może być dodatnia na dwóch przeciwległych wierzchołkach po przekątnej i ujemna na pozostałych dwóch. $skończony$ wymiar $wynosi$ , jest Z powyższej charakterystyki klas możliwych do nauczenia się PAC wynika, że ${\ displaystyle {\ mathcal {H}}}$ można nauczyć się PAC, a co za tym idzie, można się tego nauczyć.

Granice złożoności próbki

Załóżmy, $)$$klasą$ funkcji binarnych do Następnie ${\ Displaystyle {\ mathcal {H}}}$ jest ${\ Displaystyle (\ epsilon, \ delta)}$ -PAC-możliwy do nauczenia się z próbką wielkości: H {\ Displaystyle {\ mathcal {H}}}

$${\ Displaystyle N = O {\ bigg (} {\ Frac {VC ({\ mathcal {H}}) + \ ln {1 \ nad \ delta }}{\epsilon }}{\bigg )}}$$

gdzie ${\ Displaystyle VC ({\ mathcal {H}})}$ jest wymiarem VC z ${\ Displaystyle {\ mathcal {H}}}$ . Co więcej, każdy algorytm uczenia PAC dla musi mieć złożoność próbki: ${\ Displaystyle (\ epsilon, \ delta$$}$

$${\ Displaystyle N = \ Omega {\ bigg (} {\ Frac {VC ({\ mathcal {H}}) + \ ln {1 \ ponad \ delta }}{\epsilon }}{\bigg )}}$$

Zatem złożoność próbki jest funkcją liniową wymiaru VC przestrzeni hipotez.

Załóżmy, $[0,T]$$]$ { . Then, ${\mathcal {H}}$ is $(\epsilon ,\delta )$-PAC-learnable with a sample of size:

$${\ Displaystyle N = O {\ bigg (} T ^ {2} {\ Frac {PD ({\ mathcal {H }})\ln {T \over \epsilon }+\ln {1 \over \delta }}{\epsilon ^{2}}}{\bigg )}}$$

gdzie ${\ Displaystyle PD ({\ mathcal {H}})}$ jest pseudowymiarem Pollarda z ${\ Displaystyle {\ mathcal {H}}}$ .

Inne ustawienia

Oprócz ustawienia nadzorowanego uczenia się, złożoność próbki jest istotna dla problemów z uczeniem się częściowo nadzorowanym , w tym z aktywnym uczeniem się , gdzie algorytm może poprosić o etykiety dla specjalnie wybranych danych wejściowych w celu zmniejszenia kosztów uzyskania wielu etykiet. Koncepcja złożoności próbki pojawia się również w uczeniu się przez wzmacnianie , uczeniu się online i algorytmach bez nadzoru, np. w uczeniu słownikowym .

Wydajność w robotyce

Duża złożoność próbki oznacza, że ​​do przeprowadzenia wyszukiwania drzewa metodą Monte Carlo potrzebnych jest wiele obliczeń . Jest to równoznaczne z modelowym przeszukiwaniem siłowym w przestrzeni stanów. W przeciwieństwie do tego algorytm o wysokiej wydajności ma niską złożoność próbki. Możliwymi technikami zmniejszania złożoności próbki są uczenie się metryczne i uczenie się oparte na modelu.