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.