Teoria uczenia się komputerowego - Computational learning theory

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:

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ą:

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ż

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

Wybór funkcji

Wnioskowanie indukcyjne

Optymalna nauka notacji O

Negatywne wyniki

Boosting (uczenie maszynowe)

Nauka Occama

Prawdopodobnie w przybliżeniu poprawna nauka

Tolerancja błędu

Równorzędność

Opis niektórych z tych publikacji znajduje się przy ważnych publikacjach dotyczących uczenia maszynowego .

Teoria uczenia się dystrybucji

Linki zewnętrzne