Teoria uczenia się komputerowego - Computational learning theory
Część serii na |
Uczenie maszynowe i eksploracja danych |
---|
W informatyce , obliczeniowej teorii uczenia się (lub tylko teoria uczenia się ) to podpole o sztucznej inteligencji poświęcony studia projektowania i analizy uczenia maszynowego algorytmów.
Przegląd
Teoretyczne wyniki uczenia maszynowego dotyczą głównie uczenia się indukcyjnego zwanego uczeniem nadzorowanym . W uczeniu nadzorowanym algorytm otrzymuje próbki, które są oznaczone w jakiś użyteczny sposób. Na przykład próbki mogą być opisami grzybów, a etykiety mogą wskazywać, czy grzyby są jadalne, czy nie. Algorytm pobiera te wcześniej oznaczone próbki i wykorzystuje je do wywołania klasyfikatora. Ten klasyfikator to funkcja, która przypisuje etykiety do próbek, w tym próbek, które nie były wcześniej widziane przez algorytm. Celem nadzorowanego algorytmu uczenia się jest zoptymalizowanie pewnej miary wydajności, takiej jak minimalizacja liczby błędów popełnianych na nowych próbkach.
Oprócz ograniczeń wydajnościowych teoria uczenia się komputerowego bada złożoność czasową i wykonalność uczenia się. W teorii uczenia się obliczeniowego obliczenia uważa się za wykonalne, jeśli można je wykonać w czasie wielomianowym . Istnieją dwa rodzaje wyników złożoności czasowej:
- Pozytywne wyniki – Pokazanie, że pewna klasa funkcji jest możliwa do nauczenia w czasie wielomianowym.
- Wyniki negatywne – Pokazanie, że pewnych klas nie można nauczyć się w czasie wielomianowym.
Negatywne wyniki często opierają się na powszechnie uważanych, ale jeszcze niesprawdzonych założeniach, takich jak:
- Złożoność obliczeniowa – P ≠ NP (problem P versus NP) ;
- Kryptograficzne — istnieją funkcje jednokierunkowe .
Istnieje kilka różnych podejść do teorii uczenia się obliczeniowego opartych na przyjmowaniu różnych założeń dotyczących zasad wnioskowania stosowanych do uogólniania na podstawie ograniczonych danych. Należą do nich różne definicje prawdopodobieństwa (patrz prawdopodobieństwo częstotliwości , prawdopodobieństwa Bayesa ) i różnych założeń dotyczących generowania próbek. Różne podejścia obejmują:
- Dokładna nauka, zaproponowana przez Danę Angluin ;
- Prawdopodobnie w przybliżeniu poprawne uczenie ( uczenie PAC), zaproponowane przez Leslie Valiant ;
- teoria VC , zaproponowana przez Vladimira Vapnika i Alexeya Chervonenkisa ;
- wnioskowanie bayesowskie ;
- Algorytmiczna teoria uczenia się z pracy E. Marka Golda ;
- Uczenie maszynowe online , z pracy Nicka Littlestone'a.
Chociaż jej głównym celem jest abstrakcyjne zrozumienie uczenia się, teoria uczenia się komputerowego doprowadziła do opracowania praktycznych algorytmów. Na przykład teoria PAC zainspirowała wzmacnianie , teoria VC doprowadziła do wsparcia maszyn wektorowych , a wnioskowanie bayesowskie doprowadziło do powstania sieci przekonań .
Zobacz też
- Indukcja gramatyczna
- Teoria informacji
- Stabilność (teoria uczenia się)
- Tolerancja błędu (uczenie PAC)
Bibliografia
Ankiety
- Angluin, D. 1992. Teoria uczenia się komputerowego: Ankieta i wybrana bibliografia. W Proceedings of the Twenty-Fourth Annual Symposium ACM on Theory of Computing (maj 1992), strony 351–369. http://portal.acm.org/citation.cfm?id=129712.129746
- D. Hausslera. Prawdopodobnie w przybliżeniu poprawna nauka. W AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA, s. 1101–1108. Amerykańskie Stowarzyszenie na rzecz Sztucznej Inteligencji, 1990. http://citeseer.ist.psu.edu/haussler90probably.html
Wymiar VC
- V. Vapnik i A. Chervonenkis. O jednostajnej zbieżności względnych częstości zdarzeń do ich prawdopodobieństw . Teoria prawdopodobieństwa i jej zastosowania, 16(2):264–280, 1971.
Wybór funkcji
- A. Dhagat i L. Hellerstein, „Uczenie PAC z nieistotnymi atrybutami”, w „Proceedings of the IEEE Symp. o Fundacji Informatyki”, 1994. http://citeseer.ist.psu.edu/dhagat94pac.html
Wnioskowanie indukcyjne
- Złoto, E. Mark (1967). "Identyfikacja języka w limicie" (PDF) . Informacja i kontrola . 10 (5): 447–474. doi : 10.1016/S0019-9958(67)91165-5 .
Optymalna nauka notacji O
- Oded Goldreich , Dana Ron . O uniwersalnych algorytmach uczenia się . http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2224
Negatywne wyniki
- M. Kearns i Leslie Valiant . 1989. Ograniczenia kryptograficzne w uczeniu się formuł logicznych i automatów skończonych. W Proceedings of 21st Annual Symposium ACM on Theory of Computing, strony 433–444, Nowy Jork. ACM. http://citeseeer.ist.psu.edu/kearns89cryptographic.html
Boosting (uczenie maszynowe)
- Robert E. Schapire. Siła słabej zdolności do uczenia się. Uczenie maszynowe, 5(2):197-227, 1990 http://citeseer.ist.psu.edu/schapire90strength.html
Nauka Occama
- Blumer, A.; Ehrenfeucht, A.; Hausslera, D.; Warmuth, brzytwa Ockhama MK Inf.Proc.Lett. 24, 377–380, 1987.
- Blumer, A.; Ehrenfeucht, A.; Hausslera, D.; Warmuth, MK Umiejętność uczenia się i wymiar Vapnik-Chervonenkis . Dziennik ACM, 36(4):929-865, 1989.
Prawdopodobnie w przybliżeniu poprawna nauka
- L. odważny. Teoria uczenia się . Komunikaty ACM, 27(11):1134-1142, 1984.
Tolerancja błędu
- Michael Kearns i Ming Li. Nauka w obecności złośliwych błędów. SIAM Journal on Computing, 22(4):807-837, sierpień 1993. http://citeseer.ist.psu.edu/kearns93learning.html
- Kearns, M. (1993). Wydajne, odporne na zakłócenia uczenie się na podstawie zapytań statystycznych. W Proceedings of dwudziestego piątego dorocznego sympozjum ACM on Theory of Computing, strony 392–401. http://citeseeer.ist.psu.edu/kearns93efficient.html
Równorzędność
- D.Haussler, M.Kearns, N.Littlestone i M. Warmuth , Równoważność modeli uczenia wielomianowego, Proc. 1. warsztaty ACM na temat teorii uczenia się komputerowego, (1988) 42-55.
- Pitt, L.; Warmuth, MK (1990). „Redukcyjność z zachowaniem przewidywania” . Journal of Computer and System Sciences . 41 (3): 430–467. doi : 10.1016/0022-0000(90)90028-J .
Opis niektórych z tych publikacji znajduje się przy ważnych publikacjach dotyczących uczenia maszynowego .