Beräkningslärandeteori
Computational learning theory ( engelsk computational learning theory , eller helt enkelt inlärningsteori ) är ett delområde av teorin om artificiell intelligens , tillägnad utveckling och analys av maskininlärningsalgoritmer [ 1] .
Översikt
Teoretiska resultat inom maskininlärning handlar främst om induktiv inlärning, som kallas övervakad inlärning . Med detta tillvägagångssätt får algoritmen prover märkta på något sätt. Proverna kan till exempel vara beskrivningar av svamp, och etiketten avgör om svampen är ätbar eller inte. Algoritmen tar dessa märkta sampel och använder dem för att få klassificeraren . Klassificeraren är en funktion som tilldelar etiketter till prover, inklusive prover som inte tidigare har skannats av algoritmen. Målet med övervakat lärande är att optimera ett visst mått på prestanda, till exempel att minimera antalet fel som görs på nya prover.
Förutom effektivitetsgränsen studerar beräkningslärandeteori tidskomplexiteten och realiserbarheten av en algoritm. I beräkningslärandeteori sägs en beräkning vara realiserbar om den kan göras i polynomtid . Det finns två typer av tidskomplexitet för resultat:
- Positiva resultat visar att vissa klasser av funktioner kan tränas i polynomtid.
- Negativa resultat visar att vissa klasser av funktioner inte kan läras in i polynomtid.
Negativa resultat baseras ofta på vissa påståenden som man tror men förblir obevisade, till exempel:
Det finns flera olika förhållningssätt till beräkningslärandeteori. Dessa skillnader är baserade på antaganden om de slutledningsprinciper som används för att generalisera från begränsade data. Dessa principer inkluderar definitionen av sannolikhet (se frekvenssannolikhet , Bayesiansk sannolikhet ) och olika antaganden om provgenerering. Olika tillvägagångssätt inkluderar:
Beräkningslärandeteori leder till några praktiska algoritmer. Till exempel födde VPK-teorin förstärkning , Vapnik-Chervonenkis teori ledde till stöd för vektormaskiner och Bayesiansk slutledning ledde till Bayesianska nätverk (författare - Judah Pearl ).
Se även
Anteckningar
- ↑ ACL - Association for Computational Learning . Hämtad 5 december 2018. Arkiverad från originalet 25 januari 2012. (obestämd)
Litteratur
- Angluin D. Computational learning theory: Survey and Selected bibliography // Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing (maj 1992. - 1992. - P. 351-369.
- Haussler D. Förmodligen ungefär korrekt inlärning // AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA . - American Association for Artificial Intelligence, 1990. - S. 1101-1108.
- Vapnik V., Chervonenkis A. Om den enhetliga konvergensen av relativa frekvenser av händelser till deras sannolikheter // Theory of Probability and its Applications. - 1971. - T. 16 , nr. 2 . — S. 264–280 .
- Dhagat A., Hellerstein L. PAC-inlärning med irrelevanta attribut // Proceedings of the IEEE Symp. på Foundation of Computer Science . — 1994.
- E. Mark Gold. Språkidentifiering i gränsen // Information och kontroll. - 1967. - T. 10 , nr. 5 . — S. 447–474 . - doi : 10.1016/S0019-9958(67)91165-5 .
- Oded Goldreich, Dana Ron. Om universella inlärningsalgoritmer . sammanfattning
- Kearns M., Leslie Valiant. Kryptografiska begränsningar för att lära sig booleska formler och finita automater // Proceedings of the 21st Annual ACM Symposium on Theory of Computing . - New York: ACM, 1989. - S. 433-444.
- Robert E. Schapire. Styrkan med svagt lärande // Machine Learning. - 1990. - V. 5 , nr. 2 . — S. 197–227 .
- Blumer A., Ehrenfeucht A., Haussler D., Warmuth MK Occam's razor // Inf.Proc.Lett.. - 1987. - V. 24 . — S. 377–380 .
- Blumer A., Ehrenfeucht A., Haussler D., Warmuth MK Learnability and the Vapnik-Chervonenkis dimension // Journal of the ACM. - 1989. - T. 36 , nr. 4 . — S. 929–865 .
- Valiant L. A Theory of the Learnable // Communications of the ACM. - 1984. - T. 27 , nr. 11 . — S. 1134–1142 .
- Michael Kearns, Ming Li. Lärande i närvaro av skadliga fel // SIAM Journal on Computing. - 1993. - Augusti ( vol. 22 , nummer 4 ). — S. 807–837 .
- Michael Kearns. Effektivt brustolerant lärande från statistiska frågor // Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing . - 1993. - S. 392-401.
- Haussler D., Kearns M., Littlestone N., Warmuth M. Ekvivalens mellan modeller för polynominlärbarhet // Proc. Första ACM-workshopen om beräkningslärandeteori. - 1988. - S. 42-55.
- Pitt L., Warmuth MK Prediction-Preserving Reducibility // Journal of Computer and System Sciences. - 1990. - T. 41 , nr. 3 . — S. 430–467 . - doi : 10.1016/0022-0000(90)90028-J .
Länkar