Teoria de l'aprenentatge computacional

En informàtica, la teoria de l'aprenentatge computacional (o simplement teoria de l'aprenentatge) és un subcamp de la intel·ligència artificial dedicat a estudiar el disseny i l'anàlisi d'algoritmes d'aprenentatge automàtic.

Els resultats teòrics de l'aprenentatge automàtic tracten principalment d'un tipus d'aprenentatge inductiu anomenat aprenentatge supervisat. En l'aprenentatge supervisat, es donen mostres a un algorisme que s'etiqueten d'alguna manera útil. Per exemple, les mostres podrien ser descripcions de bolets i les etiquetes podrien indicar si els bolets són comestibles o no. L'algorisme pren aquestes mostres etiquetades anteriorment i les utilitza per induir un classificador. Aquest classificador és una funció que assigna etiquetes a mostres, incloses mostres que no s'han vist prèviament per l'algorisme. L'objectiu de l'algorisme d'aprenentatge supervisat és optimitzar alguna mesura del rendiment, com ara minimitzar el nombre d'errors comesos en mostres noves.

A més dels límits de rendiment, la teoria de l'aprenentatge computacional estudia la complexitat temporal i la viabilitat de l'aprenentatge. En la teoria de l'aprenentatge computacional, un càlcul es considera factible si es pot fer en temps polinomial. Hi ha dos tipus de resultats de complexitat temporal:

• Resultats positius – Mostrant que una determinada classe de funcions es pot aprendre en temps polinomial.
• Resultats negatius – Mostrant que determinades classes no es poden aprendre en temps polinomial.

Els resultats negatius sovint es basen en supòsits comuns, però encara no provats, com ara:

• Complexitat computacional – P ≠ NP (el problema P versus NP);
• Criptogràfic : existeixen funcions unidireccionals.

Hi ha diversos enfocaments diferents a la teoria de l'aprenentatge computacional basats en fer diferents supòsits sobre els principis d'inferència utilitzats per generalitzar a partir de dades limitades. Això inclou diferents definicions de probabilitat (vegeu probabilitat de freqüència, probabilitat bayesiana) i diferents supòsits sobre la generació de mostres. Els diferents enfocaments inclouen:

• Aprenentatge exacte, proposat per Dana Angluin;
• Probablement aprenentatge aproximadament correcte (aprenentatge PAC), proposat per Leslie Valiant;
• teoria VC, proposada per Vladimir Vapnik i Alexey Chervonenkis;
• Inferència bayesiana;
• Teoria de l'aprenentatge algorítmic, a partir del treball d'E. Mark Gold;
• Aprenentatge automàtic en línia, del treball de Nick Littlestone.