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 positiusMostrant que una determinada classe de funcions es pot aprendre en temps polinomial. Resultats negatiusMostrant 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.

Referències

Categoria:Aprenentatge automàtic