Teorie výpočetního učení - Computational learning theory
![]() | tento článek potřebuje další citace pro ověření.Listopadu 2018) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Část série na |
Strojové učení a dolování dat |
---|
Místa pro strojové učení |
Související články |
v počítačová věda, teorie výpočetního učení (nebo prostě teorie učení) je podpole z umělá inteligence věnovaný studiu designu a analýzy strojové učení algoritmy.[1]
Přehled
Teoretické výsledky ve strojovém učení se zabývají hlavně typem indukčního učení zvaného učení pod dohledem. V supervizovaném učení se algoritmu dají vzorky, které jsou označeny nějakým užitečným způsobem. Například vzorky mohou být popisy hub a na štítcích může být, zda jsou houby jedlé nebo ne. Algoritmus vezme tyto dříve označené vzorky a použije je k vyvolání klasifikátoru. Tento klasifikátor je funkce, která přiřazuje štítky vzorkům, včetně vzorků, které algoritmus dříve neviděl. Cílem supervizovaného algoritmu učení je optimalizovat určité měřítko výkonu, jako je minimalizace počtu chyb na nových vzorcích.
Kromě hranic výkonu studuje výpočetní teorie učení také časovou složitost a proveditelnost učení.[Citace je zapotřebí ] Teorie výpočetního učení se považuje za proveditelnou, pokud ji lze provést v polynomiální čas.[Citace je zapotřebí ] Existují dva druhy výsledků časové složitosti:
- Pozitivní výsledky - Ukazuje, že určitá třída funkcí je v polynomiálním čase naučitelná.
- Negativní výsledky - Ukazuje, že určité třídy nelze v polynomiálním čase naučit.
Negativní výsledky se často spoléhají na běžně věřené, ale dosud neprokázané předpoklady,[Citace je zapotřebí ] jako:
- Výpočetní složitost - P ≠ NP (problém P versus NP);
- Kryptografické – Jednosměrné funkce existovat.
Existuje několik různých přístupů k teorii výpočetního učení založených na vytváření různých předpokladů oodvození zásady používané k generalizaci z omezených údajů. To zahrnuje různé definice pravděpodobnost (vidět pravděpodobnost frekvence, Bayesovská pravděpodobnost ) a různé předpoklady o generování vzorků.[Citace je zapotřebí ] Mezi různé přístupy patří:[Citace je zapotřebí ]
- Přesné učení, navrhl Dana Angluin;
- Pravděpodobně přibližně správné učení (Učení PAC), navrhl Leslie Valiant;
- Teorie VC, navrhl Vladimír Vapnik a Alexey Chervonenkis;
- Bayesovský závěr;
- Algoritmická teorie učení, z práce E. Mark Gold;
- Online strojové učení, z díla Nicka Littlestone.
Zatímco jeho primárním cílem je porozumět učení abstraktně, teorie výpočetního učení vedla k vývoji praktických algoritmů. Například inspirovala teorie PAC posílení, Teorie VC vedla k podporovat vektorové stroje a Bayesianova inference vedla k sítě víry.
Viz také
Reference
Průzkumy
- Angluin, D. 1992. Teorie výpočetního učení: Průzkum a vybraná bibliografie. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (květen 1992), strany 351–369. http://portal.acm.org/citation.cfm?id=129712.129746
- D. Haussler. Pravděpodobně přibližně správné učení. V AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA, strany 1101–1108. Americká asociace pro umělou inteligenci, 1990. http://citeseer.ist.psu.edu/haussler90probably.html
VC rozměr
- V. Vapnik a A. Chervonenkis. O jednotné konvergenci relativních frekvencí událostí k jejich pravděpodobnostem. Teorie pravděpodobnosti a její aplikace, 16 (2): 264–280, 1971.
Výběr funkcí
- A. Dhagat a L. Hellerstein, „Učení PAC s irelevantními atributy“, ve sborníku IEEE Symp. o založení výpočetní techniky, 1994. http://citeseer.ist.psu.edu/dhagat94pac.html
Indukční závěr
- Gold, E. Mark (1967). „Identifikace jazyka v limitu“ (PDF). Informace a kontrola. 10 (5): 447–474. doi:10.1016 / S0019-9958 (67) 91165-5.
Optimální učení O notace
- Oded Goldreich, Dana Ron. Na univerzálních algoritmech učení. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2224
Negativní výsledky
- M. Kearns a Leslie Valiant. 1989. Kryptografická omezení učení logických vzorců a konečných automatů. In Proceedings of the 21th Annual ACM Symposium on Theory of Computing, strany 433–444, New York. ACM. http://citeseer.ist.psu.edu/kearns89cryptographic.html
Posilování (strojové učení)
- Robert E. Schapire. Síla slabé učenosti. Machine Learning, 5 (2): 197–227, 1990 http://citeseer.ist.psu.edu/schapire90strength.html
Occam Learning
- Blumer, A .; Ehrenfeucht, A .; Haussler, D .; Warmuth, M. K. Occamova břitva Inf.Proc.Lett. 24, 377–380, 1987.
- Blumer, A .; Ehrenfeucht, A .; Haussler, D .; Warmuth, M. K. Učitelnost a dimenze Vapnik-Chervonenkis. Journal of the ACM, 36 (4): 929–865, 1989.
Pravděpodobně přibližně správné učení
- L. Statečný. Teorie učitelného. Sdělení ACM, 27 (11): 1134–1142, 1984.
Tolerance chyb
- Michael Kearns a Ming Li. Učení za přítomnosti škodlivých chyb. SIAM Journal on Computing, 22 (4): 807–837, srpen 1993. http://citeseer.ist.psu.edu/kearns93learning.html
- Kearns, M. (1993). Efektivní učení odolné proti hluku ze statistických dotazů. Ve sborníku z dvacátého pátého výročního symposia ACM o teorii práce s počítači, strany 392–401. http://citeseer.ist.psu.edu/kearns93efficient.html
Rovnocennost
- D. Haussler, M. Kearns, N. Littlestone a M. Warmuth, Ekvivalence modelů pro polynomiální učitelnost, Proc. 1. ACM Workshop on Computational Learning Theory, (1988) 42-55.
- Pitt, L .; Warmuth, M. K. (1990). "Reducibilita zachovávající predikci". Journal of Computer and System Sciences. 41 (3): 430–467. doi:10.1016 / 0022-0000 (90) 90028-J.
Popis některých z těchto publikací je uveden na důležité publikace ve strojovém učení.