Co oznacza teoria uczenia się PAC?

Jestem nowy w uczeniu maszynowym. Studiuję kurs uczenia maszynowego (Uniwersytet Stanforda) i nie rozumiem, co oznacza ta teoria i jaka jest jej przydatność. Zastanawiam się, czy ktoś mógłby opisać mi tę teorię.

Ta teoria oparta jest na tym równaniu.

Prawdopodobnie w przybliżeniu poprawna teoria uczenia się pomaga w analizie, czy i pod jakimi warunkami uczeń prawdopodobnie wyda w przybliżeniu poprawny klasyfikator. (Zobaczysz, że niektóre źródła używają A zamiast L. )$L$$A$$L$

Najpierw zdefiniujmy „przybliżenie”. Hipoteza jest w przybliżeniu poprawna, jeśli jej błąd w rozkładzie wejść jest ograniczony przez niektóre ϵ , 0 ≤ ϵ ≤ $h \in H$Tj.ErrorD(h)<ϵ, gdzieDjest rozkładem na wejścia.$\epsilon, 0 \le \epsilon \le \frac{1}{2}.$$error_D(h)\lt \epsilon$$D$

Następnie „prawdopodobnie”. Jeśli wyprowadzi taki klasyfikator z prawdopodobieństwem 1 - δ , z 0 ≤ δ ≤ $L$$1 - \delta$ , nazywamy ten klasyfikatorprawdopodobnie wprzybliżeniu poprawny.$0 \le \delta \le \frac{1}{2}$

Wiedza, że ​​pojęcie celu jest możliwe do nauczenia się za pomocą PAC, pozwala ograniczyć wielkość próbki niezbędną do prawdopodobnie nauczenia się w przybliżeniu poprawnego klasyfikatora, co pokazano w utworzonej przez ciebie formule:

Aby zyskać trochę intuicji, zwróć uwagę na wpływ na gdy zmieniasz zmienne po prawej stronie. Wraz ze spadkiem dopuszczalnego błędu rośnie niezbędna wielkość próbki. Podobnie, rośnie z prawdopodobieństwem przybliżeniu prawidłowego uczący, i wielkości przestrzeni hipoteza H . (Luźno, przestrzeń hipotez jest zbiorem klasyfikatorów rozważanych przez algorytm.) Mówiąc bardziej wyraźnie, gdy rozważasz więcej możliwych klasyfikatorów lub pragniesz mniejszego błędu lub wyższego prawdopodobieństwa poprawności, potrzebujesz więcej danych, aby je rozróżnić.$m$$H$

Aby uzyskać więcej, ten i inne pokrewne filmy mogą być pomocne, podobnie jak to długie wprowadzenie lub jeden z wielu tekstów o uczeniu maszynowym , na przykład Mitchell .

Definicja prawdopodobnie w przybliżeniu poprawnej wynika z Valiant. Ma na celu podanie matematycznie rygorystycznej definicji uczenia maszynowego.
Pozwól mi trochę włóczyć się. Podczas gdy PAC używa terminu „hipoteza”, przeważnie ludzie używają słowa zamiast modelu. Z ukłonem w stronę statystyki preferuję model, ale spróbuję użyć obu. Uczenie maszynowe zaczyna się od pewnych danych i chce się znaleźć hipotezę lub model, który to powie, biorąc pod uwagę dane wejściowe x i zwracają y i lub coś bardzo zbliżonego. Co ważniejsze, biorąc pod uwagę nowe dane ˜ x model obliczy lub przewidzi odpowiednie$(x_i, y_i)$$x_i$$y_i$$\tilde{x}$ . Naprawdę nie interesuje nas, jak trafna jest hipoteza na danych (szkoleniowych), z tym wyjątkiem, że trudno uwierzyć, że model utworzony przy użyciu niektórych danych nie odzwierciedla dokładnie tego zestawu danych, ale będzie dokładny w każdej przyszłości zestawy danych. Dwa ważne zastrzeżenia polegają na tym, że nie można przewidzieć nowych danych ze 100% dokładnością, a także istnieje możliwość, że w przykładach danych, które zaobserwowano, brakuje czegoś ważnego. Przykładem zabawki jest to, że gdybym podał wam „dane” 1,2,3,4, „przewidziałby”, że 5 będzie kolejnym numerem. Jeśli przetestowałeś to, pytając ludzi, jaki jest następny numer w sekwencji, większość ludzi powiedziałaby 5. Ktośmógłby$\tilde{y}$
powiedzmy 1 000 000. Gdyby podano sekwencję 1, 2, 3, ... 999,999, jeden byłby pewien, że następna liczba to 1 000 000. Jednak następną liczbą może być 999,999,5, a nawet 5. Chodzi o to, że im więcej danych widzisz, tym bardziej pewne jest, że udało się stworzyć dokładny model, ale nigdy nie można być absolutnie pewnym.

Definicja prawdopodobnie w przybliżeniu poprawnej daje matematycznie precyzyjną wersję tego pomysłu. Biorąc pod uwagę dane z wyjściem y i oraz klasą modeli f θ, które stanowią hipotezy, można zadać 2 pytania. Czy możemy wykorzystać dane do znalezienia konkretnej hipotezy f $x_i, 1 \leq i \leq m$$y_i$$f_{\theta}$$f_{\Theta}$$p >1-\delta$$f_{\Theta}$$\epsilon$$(\delta,\epsilon)$$(\delta,\epsilon)$ i jak złożona jest dana klasa hipotez.

$\mathcal{H}$$f_{\theta}$$(\epsilon, \delta)$$0 < \epsilon,\delta , <.5$$f_{\Theta}$$\tilde{x}, \tilde{y}$$Err(f_{\Theta}(\tilde{x}) ,\tilde{y} ) < \epsilon$$p > 1-\delta$$m = m(\delta,\epsilon,\mathcal{H})$$(f_{\Theta}(\tilde{x}) -\tilde{y})^2$

$(\delta,\epsilon)$