Teorija računarskog učenja
U računarskoj nauci, teorija računarskog učenja (ili samo teorija učenja) je podoblast veštačke inteligencije posvećena proučavanju dizajna i analize algoritama mašinskog učenja.[1]
Pregled[уреди | уреди извор]
Teorijski rezultati u mašinskom učenju uglavnom se bave vrstom induktivnog učenja koje se naziva nadgledano učenje. U nadgledanom učenju, algoritmu se daju uzorci koji su označeni na neki koristan način. Na primer, uzorci mogu biti opisi pečuraka, a oznake mogu biti da li su pečurke jestive ili ne. Algoritam uzima ove prethodno označene uzorke i koristi ih da indukuje klasifikator. Ovaj klasifikator je funkcija koja dodeljuje oznake uzorcima, uključujući uzorke koje algoritam ranije nije video. Cilj algoritma nadgledanog učenja je da optimizuje neku meru performansi, kao što je minimizovanje broja grešaka napravljenih na novim uzorcima.
Pored granica performansi, teorija računarskog učenja proučava vremensku složenost i izvodljivost učenja. U teoriji računarskog učenja, proračun se smatra izvodljivim ako se može obaviti u polinomskom vremenu. Postoje dve vrste rezultata vremenske složenosti:
- Pozitivni rezultati – Pokazivanje da se određena klasa funkcija može naučiti u polinomskom vremenu.
- Negativni rezultati – Pokazuju da se određene klase ne mogu naučiti u polinomskom vremenu.
Negativni rezultati se često oslanjaju na uobičajene, ali još uvek nedokazane pretpostavke, kao što su:
- Računska složenost – P ≠ NP (problem P naspram NP);
- Kriptografske – postoje jednosmerne funkcije.
Postoji nekoliko različitih pristupa teoriji računarskog učenja zasnovanih na različitim pretpostavkama o principima zaključivanja koji se koriste za generalizaciju iz ograničenih podataka. Ovo uključuje različite definicije verovatnoće (pogledajte verovatnoću frekvencije, Bajesovu verovatnoću) i različite pretpostavke o generisanju uzoraka. Različiti pristupi uključuju:
- Tačno učenje, koje je predložila Dana Engluin;
- Verovatno približno tačno učenje (PAC učenje), koje je predložio Lesli Valijant;[2]
- VC teorija, koju su predložili Vladimir Vapnik i Aleksej Červonenkis;[3]
- Induktivno zaključivanje kako ga je razvio Raj Solomonof;[4][5]
- Algoritamska teorija učenja, iz rada E. Mark Golda;[6]
- Onlajn mašinsko učenje, iz rada Nika Litlstouna.
Dok je njen primarni cilj da apstraktno razume učenje, teorija računarskog učenja je dovela do razvoja praktičnih algoritama. Na primer, teorija PAC-a je inspirisala pristup pojačanja, VC teorija je dovela do metoda potpornih vektora, a Bajesovo zaključivanje je dovelo do razvoja Bajesovih mreža.
Reference[уреди | уреди извор]
- ^ „ACL - Association for Computational Learning”.
- ^ Valiant, Leslie (1984). „A Theory of the Learnable” (PDF). Communications of the ACM. 27 (11): 1134—1142. S2CID 12837541. doi:10.1145/1968.1972. Архивирано из оригинала (PDF) 2019-05-17. г. Приступљено 2022-11-24.
- ^ Vapnik, V.; Chervonenkis, A. (1971). „On the uniform convergence of relative frequencies of events to their probabilities” (PDF). Theory of Probability and Its Applications. 16 (2): 264—280. doi:10.1137/1116025.
- ^ Solomonoff, Ray (март 1964). „A Formal Theory of Inductive Inference Part 1”. Information and Control. 7 (1): 1—22. doi:10.1016/S0019-9958(64)90223-2
.
- ^ Solomonoff, Ray (1964). „A Formal Theory of Inductive Inference Part 2”. Information and Control. 7 (2): 224—254. doi:10.1016/S0019-9958(64)90131-7.
- ^ Gold, E. Mark (1967). „Language identification in the limit” (PDF). Information and Control. 10 (5): 447—474. doi:10.1016/S0019-9958(67)91165-5 .
Literatura[уреди | уреди извор]
- Angluin, D. 1992. Computational learning theory: Survey and selected bibliography. In Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (May 1992), pages 351–369. http://portal.acm.org/citation.cfm?id=129712.129746
- D. Haussler. Probably approximately correct learning. In AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA, pages 1101–1108. American Association for Artificial Intelligence, 1990. http://citeseer.ist.psu.edu/haussler90probably.html
- A. Dhagat and L. Hellerstein, "PAC learning with irrelevant attributes", in 'Proceedings of the IEEE Symp. on Foundation of Computer Science', 1994. http://citeseer.ist.psu.edu/dhagat94pac.html
- Oded Goldreich, Dana Ron. On universal learning algorithms. http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2224
- M. Kearns and Leslie Valiant. 1989. Cryptographic limitations on learning boolean formulae and finite automata. In Proceedings of the 21st Annual ACM Symposium on Theory of Computing, pages 433–444, New York. ACM. http://citeseer.ist.psu.edu/kearns89cryptographic.html
- Michael Kearns and Ming Li. Learning in the presence of malicious errors. SIAM Journal on Computing, 22(4):807–837, August 1993. http://citeseer.ist.psu.edu/kearns93learning.html
- Kearns, M. (1993). Efficient noise-tolerant learning from statistical queries. In Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pages 392–401. http://citeseer.ist.psu.edu/kearns93efficient.html
- D.Haussler, M.Kearns, N.Littlestone and M. Warmuth, Equivalence of models for polynomial learnability, Proc. 1st ACM Workshop on Computational Learning Theory, (1988) 42-55.
- Pitt, L.; Warmuth, M. K. (1990). „Prediction-Preserving Reducibility”. Journal of Computer and System Sciences. 41 (3): 430—467. doi:10.1016/0022-0000(90)90028-J .