Co oznacza teoria uczenia się PAC?

15

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. wprowadź opis zdjęcia tutaj

machine-learning probability pac-learning

— BetterEnglish
źródło

2

PAC oznacza prawdopodobnie w przybliżeniu poprawny.

— Marc Claesen,

@MarcClaesen, czy mógłbym to wyjaśnić w ten sposób: „Oznacza to, że metody uczenia maszynowego oferują rozwiązanie prawdopodobieństwa dla danego problemu, a to rozwiązanie jest w przybliżeniu poprawne”

— BetterEnglish

1

tutaj jest zabawny link: autonlab.org/tutorials/pac.html lub ten: autonlab.org/_media/tutorials/pac05.pdf

— EngrStudent - Przywróć Monikę

16

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ą zamiast ) $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 $h \in H$ Tj., gdziejest 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 , z $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:

m \geq \frac{1}{ϵ} (l n | H | + l n \frac{1}{δ})

$m \ge\frac{1}{\epsilon}(ln|H| + ln\frac{1}{\delta})$

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 . (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 .

— Sean Easter
źródło

To jest rodzaj odpowiedzi szukałem przez długi czas; oba proste, ale zdrowe. Chociaż wiele źródeł zapewnia obszerną odpowiedź, nie jest to tak preferowane do szybkiego odniesienia.

— Ébe Isaac

4

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 zwracają lub coś bardzo zbliżonego. Co ważniejsze, biorąc pod uwagę nowe dane 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 oraz klasą modeli które stanowią hipotezy, można zadać 2 pytania. Czy możemy wykorzystać dane do znalezienia konkretnej hipotezy $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)$

— meh
źródło