Złożoność próbki - Sample complexity

Próbka złożoność z uczenia maszynowego algorytmu reprezentuje liczbę szkoleniowo-próbek, że potrzebuje, aby skutecznie uczyć funkcji docelowej.

Dokładniej, złożoność próbki to liczba próbek uczących, które musimy dostarczyć do algorytmu, aby funkcja zwrócona przez algorytm zawierała się w arbitralnie małym błędzie najlepszej możliwej funkcji, z prawdopodobieństwem arbitralnie bliskim 1.

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

Słaby wariant naprawia określony rozkład wejścia-wyjścia;
Silny wariant bierze najgorszy przypadek złożoności próbki na wszystkie rozkłady wejścia-wyjścia.

Omówione poniżej twierdzenie „No Free Lunch” dowodzi, że na ogół silna złożoność próbki jest nieskończona, tj. nie istnieje algorytm, 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 konkretna klasa funkcji docelowych (np. tylko funkcje liniowe), to złożoność próbki jest skończona i zależy liniowo od wymiaru VC w klasie funkcji docelowych.

Definicja

Niech będzie przestrzenią, którą nazywamy przestrzenią wejściową, i niech będzie przestrzenią, którą nazywamy przestrzenią wyjściową i oznaczmy iloczyn . Na przykład, w ustawieniu klasyfikacji binarnej, jest zwykle skończenie wymiarową przestrzenią wektorową i jest zbiorem . ${\ Displaystyle X}$ ${\ Displaystyle Y}$ ${\ Displaystyle Z}$ ${\ Displaystyle X \ razy Y}$ ${\ Displaystyle X}$ ${\ Displaystyle Y}$ ${\ Displaystyle \ {-1,1 \}}$

Ustal przestrzeń hipotez funkcji . Algorytm uczący się jest przeliczaną mapą od do . Innymi słowy, jest to algorytm pobierający jako dane wejściowe skończoną sekwencję próbek uczących i wyprowadzający funkcję od do . Typowe algorytmy uczenia obejmują minimalizację ryzyka empirycznego , bez lub z regularyzacją Tichonowa . ${\ Displaystyle {\ Mathcal {H}}}$ ${\ Displaystyle h \ dwukropek X \ do Y}$ ${\ Displaystyle {\ Mathcal {H}}}$ ${\ Displaystyle Z ^ {*}}$ ${\ Displaystyle {\ Mathcal {H}}}$ ${\ Displaystyle X}$ ${\ Displaystyle Y}$

Ustal funkcję straty , na przykład stratę kwadratową , gdzie . Dla danego rozkładu na , oczekiwane ryzyko hipotezy (funkcji) wynosi ${\ Displaystyle {\ mathcal {L}} \ dwukropek Y \ razy Y \ do \ mathbb {R} _ {\ geq 0}}$ ${\ Displaystyle {\ mathcal {L}} (y, y ') = (y-y ') ^ {2}}$ $h(x)=y'$ ${\ Displaystyle \ rho}$ ${\ Displaystyle X \ razy Y}$ ${\ Displaystyle h \ w {\ matematyczny {H}}}$

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

W naszym ustawieniu mamy , gdzie jest algorytmem uczącym i jest sekwencją wektorów, które są rysowane niezależnie od . Zdefiniuj optymalne ryzyko ${\ Displaystyle h = {\ mathcal {A}} (S_ {n})}$ ${\ Displaystyle {\ Mathcal {A}}}$ ${\ Displaystyle S_ {n} = ((x_ {1}, y_ {1}), \ ldots, (x_ {n}, y_ {n})) \ sim \ rho ^ {n}}$ ${\ Displaystyle \ rho}$

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

Zestaw , dla każdego . Zauważ, że jest to zmienna losowa i zależy od zmiennej losowej , która jest pobierana z rozkładu . Algorytm nazywamy spójnym, jeśli probabilistycznie zbiega się do . Innymi słowy, dla wszystkich istnieje dodatnia liczba całkowita , taka, że dla wszystkich mamy

{\ Displaystyle h_ {n} = {\ mathcal {A}} (S_ {n})}

{\ Displaystyle n}

{\ Displaystyle h_ {n}}

S_{n}

{\ Displaystyle \ rho ^ {n}}

{\ Displaystyle {\ Mathcal {A}}}

{\ Displaystyle {\ Mathcal {E}} (h_ {n})}

{\ Displaystyle {\ mathcal {e}} _ {\ mathcal {H}} ^ {*}}

\epsilon,\delta>0

{\ Displaystyle N}

n\geq n

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

Próbka złożoność z jest to minimum , dla których ta posiada, jako funkcję i . Piszemy złożoność próbki, aby podkreślić, że ta wartość zależy od , i . Jeśli nie jest spójna , to ustawiamy . Jeżeli istnieje algorytm, dla którego jest skończony, to mówimy, że przestrzeń hipotez jest uczona .

{\ Displaystyle {\ Mathcal {A}}}

{\ Displaystyle N}

\rho,\epsilon

{\ Displaystyle \ delta}

{\ Displaystyle N (\ rho , \ epsilon , \ delta )}

{\ Displaystyle N}

\rho,\epsilon

{\ Displaystyle \ delta}

{\ Displaystyle {\ Mathcal {A}}}

{\ Displaystyle N (\ rho , \ epsilon , \ delta ) = \ infty }

{\ Displaystyle N (\ rho , \ epsilon , \ delta )}

{\ Displaystyle {\ Mathcal {H}}}

Innymi słowy, złożoność próbki określa stopień spójności algorytmu: przy pożądanej dokładności i pewności należy próbkować punkty danych, aby zagwarantować, że ryzyko funkcji wyjściowej mieści się w najlepszym możliwym zakresie, z prawdopodobieństwem co najmniej . ${\ Displaystyle N (\ rho , \ epsilon , \ delta )}$ $\epsilon$ ${\ Displaystyle \ delta}$ ${\ Displaystyle N (\ rho , \ epsilon , \ delta )}$ $\epsilon$ $1-\delta$

W prawdopodobnie w przybliżeniu poprawnym (PAC) uczeniu , chodzi o to, czy złożoność próbki jest wielomianowa , to znaczy, czy jest ograniczona wielomianem w i . Jeśli dla jakiegoś algorytmu uczącego jest wielomianem, to mówi się, że przestrzeń hipotez jest

możliwa do nauczenia przez PAC . Zauważ, że jest to silniejsze pojęcie niż umiejętność uczenia się.

{\ Displaystyle N (\ rho , \ epsilon , \ delta )}

1/\epsilon

1/\delta

{\ Displaystyle N (\ rho , \ epsilon , \ delta )}

{\ Displaystyle {\ Mathcal {H}}}

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

Można zapytać, czy istnieje algorytm uczenia się, aby złożoność próbki była skończona w sensie silnym, to znaczy, że istnieje ograniczenie liczby próbek potrzebnych, aby algorytm mógł nauczyć się dowolnego rozkładu w przestrzeni wejścia-wyjścia z określony błąd docelowy. Bardziej formalnie, ktoś pyta, czy istnieje algorytm uczenia się , taki, że dla wszystkich istnieje dodatnia liczba całkowita, taka, że dla wszystkich mamy ${\ Displaystyle {\ Mathcal {A}}}$ $\epsilon,\delta>0$ ${\ Displaystyle N}$ $n\geq n$

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

gdzie , jak wyżej. Twierdzenie „ No Free Lunch” mówi, że bez ograniczeń przestrzeni hipotez tak nie jest, tzn. zawsze istnieją „złe” rozkłady, dla których złożoność próbki jest arbitralnie duża.

{\ Displaystyle h_ {n} = {\ mathcal {A}} (S_ {n})}

{\ Displaystyle S_ {n} = ((x_ {1}, y_ {1}), \ ldots, (x_ {n}, y_ {n})) \ sim \ rho ^ {n}}

{\ Displaystyle {\ Mathcal {H}}}

Tak więc, aby sformułować twierdzenia o szybkości zbieżności wielkości

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

trzeba albo

ograniczać przestrzeń rozkładów prawdopodobieństwa , np. poprzez podejście parametryczne, lub ${\ Displaystyle \ rho}$
ograniczają przestrzeń hipotez , tak jak w podejściach bezdystrybucyjnych. ${\ Displaystyle {\ Mathcal {H}}}$

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

To ostatnie podejście prowadzi do koncepcji takich jak wymiar VC i złożoność Rademachera, które kontrolują złożoność przestrzeni . Mniejsza przestrzeń dla hipotez wprowadza do procesu wnioskowania więcej błędu systematycznego, co oznacza, że może być większe niż najlepsze możliwe ryzyko w większej przestrzeni. Jednak poprzez ograniczenie złożoności przestrzeni hipotez staje się możliwe, aby algorytm wytwarzał bardziej jednorodnie spójne funkcje. Ten kompromis prowadzi do koncepcji

regularyzacji .

{\ Displaystyle {\ Mathcal {H}}}

{\ Displaystyle {\ mathcal {e}} _ {\ mathcal {H}} ^ {*}}

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

${\ Displaystyle {\ Mathcal {H}}}$ można się nauczyć PAC.
Wymiar VC jest skończony. ${\ Displaystyle {\ Mathcal {H}}}$
${\ Displaystyle {\ Mathcal {H}}}$ to jednolita klasa Gliveenko-Cantelli .

Daje to sposób na udowodnienie, że pewne przestrzenie hipotez można nauczyć się PAC, a co za tym idzie, można się nauczyć.

Przykład przestrzeni hipotezy do nauczenia PAC

${\ Displaystyle X = \ mathbb {R} ^ {d}, Y = \ {-1, 1 \}}$ , i niech będzie przestrzenią funkcji afinicznych na , czyli funkcji formy dla niektórych . Jest to klasyfikacja liniowa z problemem uczenia offsetowego. Zwróćmy teraz uwagę, że cztery współpłaszczyznowe punkty w kwadracie nie mogą zostać zniszczone przez żadną funkcję afiniczną, ponieważ żadna funkcja afiniczna nie może być dodatnia na dwóch przeciwległych po przekątnej wierzchołkach i ujemna na pozostałych dwóch. Zatem wymiar VC jest , więc jest skończony. Wynika to z powyższej charakterystyki klas uczących się przez PAC, które są uczące się przez PAC, a co za tym idzie, uczące się. ${\ Displaystyle {\ Mathcal {H}}}$ ${\ Displaystyle X}$ ${\ Displaystyle x \ mapsto \ langle w, x \ rangle + b}$ ${\ Displaystyle w \ w \ mathbb {R} ^ {d}, b \ w \ mathbb {R}}$ ${\ Displaystyle {\ Mathcal {H}}}$ $d+1$ ${\ Displaystyle {\ Mathcal {H}}}$

Granice złożoności próbki

Załóżmy, że jest klasą funkcji binarnych (funkcje do ). Następnie można się nauczyć -PAC z próbką o rozmiarze: ${\ Displaystyle {\ Mathcal {H}}}$ ${\ Displaystyle \ {0,1 \}}$ ${\ Displaystyle {\ Mathcal {H}}}$ $(\epsilon,\delta)$

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

gdzie jest wymiar VC z . Co więcej, każdy algorytm uczenia -PAC dla musi mieć złożoność próbki:

{\ Displaystyle VC ({\ mathcal {H}})}

{\ Displaystyle {\ Mathcal {H}}}

(\epsilon,\delta)

{\ Displaystyle {\ Mathcal {H}}}

{\ Displaystyle N = \ Omega {\ bigg (}{\ Frac {VC ({\ mathcal {H}}) + \ ln {1 \ nad \ delta}} {\ epsilon}} {\ duży}}}

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

Załóżmy, że jest to klasa funkcji o wartościach rzeczywistych z zakresem w . Następnie można się nauczyć -PAC z próbką o rozmiarze: ${\ Displaystyle {\ Mathcal {H}}}$ ${\ Displaystyle [0, T]}$ ${\ Displaystyle {\ Mathcal {H}}}$ $(\epsilon,\delta)$

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

gdzie jest Pollard pseudo-wymiar z .

{\ Displaystyle PD ({\ mathcal {H}})}

{\ Displaystyle {\ Mathcal {H}}}

Inne ustawienia

Oprócz ustawienia nadzorowanego uczenia się, złożoność próbki jest istotna w przypadku problemów związanych z

uczeniem się częściowo nadzorowanym , w tym z uczeniem aktywnym , gdzie algorytm może poprosić o etykiety dla specjalnie wybranych danych wejściowych w celu zmniejszenia kosztów uzyskania wielu etykiet. Pojęcie złożoności próbki pokazuje również w nauce zbrojenia , kształcenia online i algorytmów bez nadzoru, np słowniku nauki .

Efektywność w robotyce

Wysoka złożoność próbki oznacza, że do uruchomienia przeszukiwania drzewa metodą

Monte Carlo potrzeba wielu obliczeń . Jest to równe modelowi swobodnego przeszukiwania siłowego 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 metryczne i uczenie ze wzmacnianiem w oparciu o model.

Languages

In other projects