Prawidłowe uczenie się PAC granice wymiarów VC

Dobrze wiadomo, że w przypadku klasy koncepcyjnej $\mathcal{C}$ o wymiarze VC wystarczy uzyskać przykłady oznaczone PAC learn . Nie jest dla mnie jasne, czy algorytm uczenia się PAC (który wykorzystuje tak wiele próbek) jest właściwy, czy niewłaściwy? W podręcznikach Kearnsa i Vazirani oraz Anthony'ego i Biggsa wydaje się, że algorytm uczenia się PAC jest niewłaściwy (tj. Hipoteza wyjściowa nie leży w )O ( $d$C$O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$$\mathcal{C}$$\mathcal{C}$

1. Czy ktoś może wyjaśnić, czy podobna górna granica ma również zastosowanie do właściwego ustawienia uczenia się PAC? Jeśli tak, czy możesz podać mi odniesienie, w którym jest to wyraźnie wspomniane, a także zawiera samodzielny dowód?

2. Ostatnio Hanneke poprawił tę granicę, pozbywając się czynnika . Czy ktoś może wyjaśnić, czy wiadomo, że jest usuwalny dla ustawienia uczenia się właściwego PAC? Czy jest to wciąż pytanie otwarte?log ( 1 / ε $\log(1/\varepsilon)$$\log(1/\varepsilon)$

Dziękuję Aryehowi za zwrócenie mojej uwagi na to pytanie.

Jak wspomnieli inni, odpowiedź na (1) brzmi „ Tak” , a prosta metoda minimalizacji ryzyka empirycznego w $\mathcal{C}$ pozwala uzyskać złożoność próbki $O((d/\varepsilon)\log(1/\varepsilon))$ (patrz Vapnik i Chervonenkis, 1974; Blumer, Ehrenfeucht, Haussler i Warmuth, 1989).

Jeśli chodzi o (2), w rzeczywistości wiadomo, że istnieją przestrzenie $\mathcal{C}$ których żaden właściwy algorytm uczenia się nie osiąga lepszej złożoności próbki niż $\Omega((d/\varepsilon)\log(1/\varepsilon))$ , a zatem prawidłowe uczenie się nie może osiągnąć optymalnego $O(d/\varepsilon)$ złożoność próby. O ile mi wiadomo, fakt ten nigdy nie został opublikowany, ale jest zakorzeniony w pokrewnym argumencie Daniely'ego i Shaleva-Shwartza (COLT 2014) (pierwotnie sformułowanym dla innego, ale pokrewnego pytania w uczeniu się wieloklasowym).

Rozważmy Prosty przykład $d=1$ , i umieścić w przestrzeni $\mathcal{X}$ jako $\{1,2,...,1/\varepsilon\}$ , a $\mathcal{C}$ to singletony $f_z(x) := \mathbb{I}[x = z], z \in \mathcal{X}$ : to znaczy, każdy klasyfikator w $\mathcal{C}$ klasyfikuje dokładnie jeden punkt od $\mathcal{X}$ jako $1$ a pozostałe jako $0$. Na dolnej granicy, należy docelową funkcję jako losowej jednoelementowy $f_{x^*}$ , gdzie $x^{*} \sim {\rm Uniform}(\mathcal{X})$ i $P$ krańcowa rozkład $X$ jest jednolity o $\mathcal{X}\setminus\{x^*\}$ . Teraz uczeń nigdy nie widzi żadnych przykładów oznaczonych jako $1$ , ale musi wybrać punkt $z$ aby odgadnąć, że ma oznaczenie $1$ (co ważne, funkcja `` wszystko zero '' nie znajduje się w $\mathcal{C}$Tak dowolny właściwy uczący musi że niektórzy $z$ ), i dopiero widoczne każdym punkcie $\mathcal{X}\setminus\{x^*\}$ ma co najmniej $1/2$ możliwość zgadywania źle (czyli tylnej prawdopodobieństwo ich $f_z$ o $z \neq x^*$ co najmniej $1/2$ ). Argument kolektora kuponów sugeruje, że wymagałby $\Omega((1/\varepsilon)\log(1/\varepsilon))$próbki, aby zobaczyć każdy punkt w $\mathcal{X} \setminus \{x^*\}$ . Dowodzi to dolnej granicy $\Omega((1/\varepsilon)\log(1/\varepsilon))$ dla wszystkich właściwych uczniów.

Dla ogólnej $d>1$ bierzemy $\mathcal{X}$ jako $\{1,2,...,d/(4\varepsilon)\}$ , weź $\mathcal{C}$ jako klasyfikatory $\mathbb{I}_{A}$ dla zbiorów $A \subset \mathcal{X}$ o rozmiarze dokładnie $d$ , wybierz losowo funkcję docelową z $\mathcal{C}$ i ponownie przyjmij $P$ jako jednolity tylko w punktach, które funkcja docelowa klasyfikuje $0$ ( więc uczący się nigdy nie widzi punktu oznaczonego jako $1$). Zatem uogólnienie argumentu kupca-kolektora sugeruje, że potrzebujemy próbek $\Omega((d/\varepsilon)\log(1/\varepsilon))$ aby zobaczyć przynajmniej $|\mathcal{X}| - 2d$ różne punkty z $\mathcal{X}$ i bez obejrzeniu tego wiele różnych punktach dowolny właściwy uczący przynajmniej $1/3$ szanse na uzyskanie większych niż $d/4$ jego przypuszczalne $A$ do $d$ punkty niesłusznie wybrany hipotezy $h_{A}$, co oznacza, że ​​jego poziom błędu jest większy niż $\varepsilon$ . Zatem w tym przypadku nie ma odpowiedniego ucznia o złożoności próbki mniejszej niż $\Omega((d/\varepsilon)\log(1/\varepsilon))$ , co oznacza, że ​​żaden uczący się nie osiąga optymalnej złożoności próbki $O(d/\varepsilon)$ .

Zauważ, że wynik jest dość specyficzny dla skonstruowanej przestrzeni $\mathcal{C}$Istnieją przestrzenie $\mathcal{C}$ których właściwi uczniowie mogą osiągnąć optymalną złożoność próbki $O(d/\varepsilon)$ , a nawet dokładne pełne wyrażenie $O((d/\varepsilon)+(1/\varepsilon)\log(1/\delta))$ z ( Hanneke, 2016a). Niektóre górne i dolne granice dla ogólnych uczniów ERM zostały opracowane w (Hanneke, 2016b), skwantyfikowane pod względem właściwości przestrzeni $\mathcal{C}$, a także omawianie bardziej wyspecjalizowanych przypadków, w których konkretni właściwi uczniowie mogą czasami osiągnąć optymalną złożoność próby.

Bibliografia:

Vapnik and Chervonenkis (1974). Teoria rozpoznawania wzorców. Nauka, Moskwa, 1974.

Blumer, Ehrenfeucht, Haussler i Warmuth (1989). Uczenie się i wymiar Vapnika-Chervonenkisa. Journal of the Association for Computing Machinery, 36 (4): 929–965.

Daniely i Shalev-Shwartz (2014). Optymalni uczniowie dla problemów wieloklasowych. W materiałach z 27. Konferencji na temat teorii uczenia się.

Hanneke (2016a). Optymalna złożoność próby uczenia się PAC. Journal of Machine Learning Research, t. 17 (38), s. 1–15.

Hanneke (2016b). Udoskonalone granice błędów dla kilku algorytmów uczenia się. Journal of Machine Learning Research, t. 17 (135), s. 1–55.

Twoje pytania (1) i (2) są powiązane. Najpierw porozmawiajmy o właściwej nauce PAC. Wiadomo, że istnieją odpowiednie osoby uczące się PAC, które osiągają zerowy błąd próbki, a mimo to wymagają przykłady. Dla prostego dowoduzależnościϵrozważ klasę przedziałów[a,b]⊆[0,1]w rozkładzie równomiernym. Jeśli wybierzemynajmniejszyspójny przedział, rzeczywiście otrzymamy próbkę złożonościO(1/ϵ). Załóżmy jednak, że wybieramynajwiększyspójny przedział, a pojęciem docelowym jest przedział punktowy, taki jak[0,0$\Omega(\frac{d}{\epsilon}\log\frac1\epsilon)$$\epsilon$$[a,b]\subseteq[0,1]$$O(1/\epsilon)$$[0,0]$. Następnie prosty argument zbierający kupony pokazuje, że jeśli nie otrzymamy mniej więcej przykładów, oszukuje nas odstęp między negatywnymi przykładami (jedyny rodzaj, jaki zobaczymy) - który ma charakterystyczne zachowanie1/[wielkość próby] pod rozkładem jednolitym. Bardziej ogólne dolne granice tego typu podano w$\frac{1}{\epsilon}\log\frac1\epsilon$$1/$

P. Auer, R. Ortner. Nowy PAC związany dla klas koncepcyjnych zamkniętych skrzyżowaniami. Machine Learning 66 (2-3): 151-163 (2007) http://personal.unileoben.ac.at/rortner/Pubs/PAC-intclosed.pdf

Właściwe PAC polega na tym, że dla pozytywnych wyników w przypadku abstrakcyjnym nie można określić algorytmu poza ERM, który mówi „znaleźć koncepcję zgodną z oznaczoną próbką”. Gdy masz dodatkową strukturę, taką jak interwały, możesz zbadać dwa różne algorytmy ERM, jak wyżej: minimalny vs. maksymalny spójny segment. I mają one różne złożone próbki!

Moc niewłaściwego PAC polega na tym, że możesz projektować różne schematy głosowania (taki jest wynik Hanneke) - a ta dodatkowa struktura pozwala udowodnić poprawę stawek. (Historia jest prostsza dla agnostycznego PAC, w którym ERM zapewnia najlepszy możliwy wskaźnik najgorszego przypadku, aż do stałych.)

Edytować. Teraz przychodzi mi do głowy, że strategia prognozowania grafu 1-inkluzji D. Hausslera, N. Littlestone'a, Md K. Warmutha. Prognozowanie {0,1} -funkcje losowych punktów. Inf. Comput. 115 (2): 248-292 (1994) może być naturalnym kandydatem do uniwersalnego właściwa uczący pac.$O(d/\epsilon)$

Aby dodać do obecnie akceptowanej odpowiedzi:

1. Tak.

   $$O\left(\frac{d}{\varepsilon}\log\frac{1}{\varepsilon}\right)$$ $\mathsf{NP}=\mathsf{RP}$$L$$\mathcal{H}=\mathcal{C}$

2. $\log(1/\varepsilon)$

   $\log(1/\varepsilon)$$(\varepsilon, \delta)$

   (Przypis 1 w tym samym dokumencie jest również istotny)

[1] A. Blumer, A. Ehrenfeucht, D. Haussler i MK Warmuth. Uczenie się i wymiar Vapnika-Chervonenkisa. Journal of the ACM, 36 (4): 929–965, 1989.

[2] S. Hanneke. Optymalna złożoność próby uczenia się PAC. J. Mach. Uczyć się. Res. 17, 1, 1319–1333, 2016.

[3] S. Arunachalam i R. de Wolf. Optymalna złożoność próbek kwantowych algorytmów uczenia się. W materiałach z 32. konferencji złożoności obliczeniowej (CCC), 2017.