En teoría de aprendizaje computacional, el aprendizaje correcto probablemente aproximado (Aprendizaje PAC) (en inglés probably approximately correct learning) es un marco para el análisis matemático de aprendizaje de máquina.
Este fue propuesto en 1984 por Leslie Valiant.
[1] En este marco, la técnica de aprendizaje recibe muestras y debe seleccionar una función de generalización (llamado la hipótesis) de cierta clase de funciones posibles.
El objetivo es que, con una alta probabilidad (la parte del "probablemente"), la función seleccionada tenga un error de generalización bajo (la parte del "correcto aproximado").
El modelo fue más tarde extendido para tratar ruido (muestras mal clasificadas).
En particular, se espera que la técnica de aprendizaje encuentre funciones eficientes (en tiempo y requisitos espaciales limitados a un polinomio del tamaño del ejemplo), y la técnica de aprendizaje en sí debe implementar un procedimiento eficiente (que exige un recuento limitado a un polinomio de la medida del concepto, modificado por los límites de aproximación y de probabilidad).
Con el fin de dar a la definición de algo que es Aprendizaje PAC, primero tenemos que introducir algunas terminologías.
[2][3] Para las siguientes definiciones, se usarán dos ejemplos.
bits que codifican una imagen binaria-valor.
El otro ejemplo es el problema de encontrar un intervalo que clasificará correctamente los puntos dentro del intervalo como positivo y los puntos exteriores al rango como negativo.
Sea X un conjunto llamado el espacio de instancia o la codificación de todas las muestras, y cada instancia tiene la longitud asignada.
En el problema de reconocimiento del caracteres, el espacio de instancia es
En el problema de intervalo el espacio de instancia es X = R , dónde R denota el conjunto de todos los números reales.
que codifican una imagen de la letra "P".
un procedimiento que dibuja un ejemplo,
, utilizando una distribución de probabilidad
y da la etiqueta correcta
y 0 en otro caso Digamos que hay un algoritmo
que da acceso a la
que, con probabilidad de al menos
que tiene de media errores menores o igual a
Si hay tal algoritmo para cada concepto
, y siempre se cumple que
es un algoritmo PAC de aprendizaje para
ejemplos y requiere como máximo
Una clase concepto es aprendizaje PAC eficiente si es PAC aprendible por un algoritmo que se ejecuta en tiempo polinomial en
Bajo ciertas condiciones de regularidad estas tres condiciones son equivalentes: