Aprenentatge aproximadament correcte

En la teoria de l'aprenentatge computacional, probablement l'aprenentatge aproximadament correcte (amb acrònim anglès PAC) és un marc per a l'anàlisi matemàtica de l'aprenentatge automàtic. Va ser proposat l'any 1984 per Leslie Valiant.

En aquest marc, l'alumne rep mostres i ha de seleccionar una funció de generalització (anomenada hipòtesi) d'una determinada classe de funcions possibles. L'objectiu és que, amb alta probabilitat (la part "probablement"), la funció seleccionada tingui un error de generalització baix (la part "aproximadament correcta"). L'alumne ha de ser capaç d'aprendre el concepte donada qualsevol relació d'aproximació arbitrària, probabilitat d'èxit o distribució de les mostres.

Més tard, el model es va ampliar per tractar el soroll (mostres mal classificades).

Una innovació important del marc PAC és la introducció de conceptes de teoria de la complexitat computacional a l'aprenentatge automàtic. En particular, s'espera que l'alumne trobi funcions eficients (requisits de temps i espai limitats a un polinomi de la mida de l'exemple), i el propi aprenent ha d'implementar un procediment eficient (que requereix un recompte d'exemple limitat a un polinomi de la mida del concepte, modificat per l'aproximació i els límits de versemblança).

Per tal de donar la definició d'alguna cosa que es pot aprendre amb PAC, primer hem d'introduir una mica de terminologia.

Per a les definicions següents, s'utilitzaran dos exemples. El primer és el problema del reconeixement de caràcters donat una sèrie de $n$ bits que codifiquen una imatge de valors binaris. L'altre exemple és el problema de trobar un interval que classificarà correctament els punts dins de l'interval com a positius i els punts fora de l'interval com a negatius.