Prawdopodobnie w przybliżeniu poprawna nauka - Probably approximately correct learning

Część serii na
Uczenie maszynowe i eksploracja danych
Problemy Klasyfikacja Grupowanie Regresja Wykrywanie anomalii Czyszczenie danych AutoML Zasady stowarzyszenia Nauka wzmacniania Prognoza strukturalna Inżynieria funkcji Nauka funkcji Nauka online Nauka częściowo nadzorowana Nauka nienadzorowana Nauka rangi Indukcja gramatyczna
Uczenie nadzorowane ( klasyfikacja  • regresja ) Drzewa decyzyjne Zespoły Parcianka Wzmacnianie Losowy las k -NN Regresja liniowa Naiwny Bayes Sztuczne sieci neuronowe Regresja logistyczna Perceptron Maszyna wektorów trafności (RVM) Maszyna wektorów pomocniczych (SVM)
Grupowanie BRZOZOWY LECZYĆ Hierarchiczny k -oznacza Oczekiwanie – maksymalizacja (EM) DBSCAN OPTYKA Średnia zmiana
Redukcja wymiarowości Analiza czynników CCA ICA LDA NMF PCA PGD t-SNE
Prognoza strukturalna Modele graficzne Sieć Bayesa Warunkowe pole losowe Ukryty Markow
Wykrywanie anomalii k -NN Lokalny czynnik odstający
Sztuczna sieć neuronowa Autokoder Obliczenia kognitywne Głęboka nauka DeepDream Perceptron wielowarstwowy RNN LSTM GRU ESN Ograniczona maszyna Boltzmanna GAN SOM Konwolucyjna sieć neuronowa U-Net Transformator Wzrastająca sieć neuronowa Memtranzystor Elektrochemiczna pamięć RAM (ECRAM)
Nauka wzmacniania Q-learning SARSA Różnica czasowa (TD)
Teoria Kompromis między odchyleniami a wariancją Teoria uczenia się komputerowego Minimalizacja ryzyka empirycznego Nauka Occam Nauka PAC Nauka statystyczna Teoria VC
Miejsca uczenia maszynowego NeuroIPS ICML ML JMLR ArXiv:cs.LG
Powiązane artykuły Słowniczek sztucznej inteligencji Lista zbiorów danych do badań nad uczeniem maszynowym Zarys uczenia maszynowego
v T mi

W teorii uczenia komputerowego , prawdopodobnie w przybliżeniu poprawne ( PAC ) uczenie jest podstawą matematycznej analizy uczenia maszynowego . Zaproponował ją w 1984 Leslie Valiant .

W tych ramach uczący się otrzymuje próbki i musi wybrać funkcję uogólnienia (zwaną hipotezą ) z pewnej klasy możliwych funkcji. Celem jest, aby z dużym prawdopodobieństwem (część „prawdopodobnie”) wybrana funkcja miała niski błąd uogólnienia (część „w przybliżeniu poprawna”). Osoba ucząca się musi być w stanie nauczyć się pojęcia przy dowolnym współczynniku aproksymacji, prawdopodobieństwie sukcesu lub rozkładzie próbek .

Model został później rozszerzony o obróbkę szumu (błędnie sklasyfikowane próbki).

Ważną innowacją w ramach PAC jest wprowadzenie koncepcji teorii złożoności obliczeniowej do uczenia maszynowego. W szczególności oczekuje się, że uczący się znajdzie efektywne funkcje (wymagania czasowe i przestrzenne związane z wielomianem wielkości przykładu), a sam uczący się musi zaimplementować wydajną procedurę (wymagającą liczby przykładów związanych z wielomianem wielkości pojęciowej, zmodyfikowanej przez aproksymację i granice prawdopodobieństwa ).

Definicje i terminologia

Aby podać definicję czegoś, czego można się nauczyć przez PAC, musimy najpierw wprowadzić pewną terminologię.

Dla poniższych definicji zostaną użyte dwa przykłady. Pierwszym z nich jest problem rozpoznawania znaków na podstawie tablicy bitów kodujących obraz o wartości binarnej. Drugim przykładem jest problem ze znalezieniem przedziału, który poprawnie zaklasyfikuje punkty w przedziale jako dodatnie, a punkty spoza przedziału jako ujemne. ${\ Displaystyle n}$

Niech będzie zbiorem zwanym przestrzenią instancji lub kodowaniem wszystkich próbek. W problemie rozpoznawania znaków przestrzeń instancji to . W zadaniu przedziałowym przestrzeń instancji, , jest zbiorem wszystkich ograniczonych przedziałów w , gdzie oznacza zbiór wszystkich liczb rzeczywistych . ${\ Displaystyle X}$${\ Displaystyle X = \ {0,1 \} ^ {n}}$${\ Displaystyle X}$${\ Displaystyle \ mathbb {R}}$${\ Displaystyle \ mathbb {R}}$

Koncepcja jest podzbiorem . Jedną z koncepcji jest zestaw wszystkich wzorców bitów, w których koduje się obraz litery „P”. Przykładową koncepcją z drugiego przykładu jest zbiór otwartych przedziałów , z których każdy zawiera tylko punkty dodatnie. Klasa pojęcie to zbiór pojęć ponad . Może to być zestaw wszystkich podzbiorów tablicy bitów, które są połączone w szkielet 4 (szerokość czcionki wynosi 1). ${\displaystyle c\podzbiór X}$${\ Displaystyle X = \ {0,1 \} ^ {n}}$${\displaystyle \{(a,b)\mid 0\leq a\leq \pi/2,\pi \leq b\leq {\sqrt {13}}\}}$ ${\ Displaystyle C}$${\ Displaystyle X}$

Niech będzie procedurą, która rysuje przykład , używając rozkładu prawdopodobieństwa i daje poprawną etykietę , czyli 1 jeśli i 0 w przeciwnym razie. ${\displaystyle EX(c,D)}$${\displaystyle x}$${\ Displaystyle D}$${\displaystyle c(x)}$${\displaystyle x\wc}$

Teraz załóżmy, że istnieje algorytm i wielomian w (oraz inne istotne parametry klasy ) takie, że przy danej próbce o rozmiarze wylosowanej zgodnie z , to z prawdopodobieństwem co najmniej , wyprowadza hipotezę, która ma średni błąd mniejsze lub równe on przy tym samym rozkładzie . Dalej, jeśli powyższe stwierdzenie dla algorytmu jest prawdziwe dla każdego pojęcia i dla każdej dystrybucji ponad , i dla wszystkich, wtedy jest (efektywnie) uczący się PAC (lub uczący się PAC bez dystrybucji ). Możemy również powiedzieć, że jest to algorytm uczenia PAC dla . ${\displaystyle 0<\epsilon,\delta <1}$${\ Displaystyle A}$${\displaystyle p}$${\displaystyle 1/\epsilon,1/\delta}$${\ Displaystyle C}$${\displaystyle p}$${\displaystyle EX(c,D)}$${\displaystyle 1-\delta}$${\ Displaystyle A}$${\displaystyle h\w C}$${\displaystyle \epsilon}$${\ Displaystyle X}$${\ Displaystyle D}$${\ Displaystyle A}$${\displaystyle c\w C}$${\ Displaystyle D}$${\ Displaystyle X}$${\displaystyle 0<\epsilon,\delta <1}$${\ Displaystyle C}$${\ Displaystyle A}$${\ Displaystyle C}$

Równorzędność

W pewnych warunkach regularności warunki te są równoważne:

1. Koncepcji klasy C można się nauczyć PAC.
2. Wymiar VC z C jest skończona.
3. C to jednolita klasa Glivenka–Cantelli .
4. C jest ściśliwe w sensie Littlestone i Warmuth

Zobacz też

• Nauka Occam
• Nauczanie maszynowe
• Eksploracja danych
• Tolerancja błędu (uczenie PAC)
• Złożoność próbki

Bibliografia

https://users.soe.ucsc.edu/~manfred/pubs/lrnk-olivier.pdf

Moran, Shay; Yehudayoff, Amir (2015). „Przykładowe schematy kompresji dla klas VC”. arXiv : 1503.06960 [ cs.LG ].

Dalsza lektura

• M. Kearns, U. Vazirani. Wprowadzenie do obliczeniowej teorii uczenia się . MIT Press, 1994. Podręcznik.
• M. Mohri, A. Rostamizadeh i A. Talwalkar. Podstawy uczenia maszynowego . MIT Press, 2018. Rozdział 2 zawiera szczegółowe omówienie możliwości uczenia się PAC. Czytelny dzięki otwartemu dostępowi od wydawcy.
• D. Hausslera. Omówienie schematu nauczania prawdopodobnie w przybliżeniu poprawnego (PAC) . Wprowadzenie do tematu.
• L. odważny. Prawdopodobnie w przybliżeniu poprawne. Basic Books, 2013. W którym Valiant twierdzi, że uczenie się PAC opisuje, w jaki sposób organizmy ewoluują i uczą się.