Aprendizaje PAC

En teoría de aprendizaje computacional, aprendizaje correcto probablemente aproximado (Aprendizaje PAC) (en inglés probably approximately correct learning) es un marco para análisis matemático de aprendizaje de máquina. Este fue propuesto en 1984 por Leslie Valiant.​ En este marco, la técnica de aprendizaje recibe muestras y debe seleccionar una función de generalización (llamado la hipótesis) de una clase segura de funciones posibles. El objetivo es que, con una alta probabilidad (la parte del "probablemente"), la función seleccionada tendrá un error de generalización bajo (la parte del "correcto aproximado"). La técnica de aprendizaje tiene que ser capaz de aprender el concepto dado cualquier proporción de aproximación arbitraria, probabilidad de éxito, o distribución de las muestras. El modelo fue más tarde extendido para tratar ruido (muestras mal clasificadas). Una innovación importante al marco del PAC es la introducción de los conceptos de la teoría de la complejidad computacional de aprendizaje automático. 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 si 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).