Probablemente aprendizaje aproximadamente correcto
En la teoría del aprendizaje computacional , el aprendizaje probablemente aproximadamente correcto ( PAC ) es un marco para el análisis matemático del aprendizaje automático . Fue propuesto en 1984 por Leslie Valiant . [1]
En este marco, el alumno recibe muestras y debe seleccionar una función de generalización (llamada hipótesis ) de una cierta clase de funciones posibles. El objetivo es que, con alta probabilidad (la parte "probablemente"), la función seleccionada tenga un error de generalización bajo (la parte "aproximadamente correcta"). El alumno debe ser capaz de aprender el concepto dada cualquier proporción de aproximación arbitraria, probabilidad de éxito o distribución de las muestras .
Una innovación importante del marco PAC es la introducción de conceptos de la teoría de la complejidad computacional al aprendizaje automático. En particular, se espera que el alumno encuentre funciones eficientes (requisitos de tiempo y espacio acotados a un polinomio del tamaño del ejemplo), y el propio aprendiz debe implementar un procedimiento eficiente (que requiera un conteo de ejemplos acotado a un polinomio del tamaño del concepto, modificado por los límites de aproximación y verosimilitud ).
Para dar la definición de algo que se puede aprender en PAC, primero tenemos que introducir alguna terminología. [2] [3]
Para las siguientes definiciones, se utilizarán dos ejemplos. El primero es el problema del reconocimiento de caracteres dada una serie de bits que codifican una imagen con valores binarios. El otro ejemplo es el problema de encontrar un intervalo que clasifique correctamente los puntos dentro del intervalo como positivos y los puntos fuera del rango como negativos.
Sea un conjunto llamado espacio de instancia o la codificación de todas las muestras. En el problema de reconocimiento de caracteres, el espacio de instancia es . En el problema del intervalo, el espacio de instancia, , es el conjunto de todos los intervalos acotados en , donde denota el conjunto de todos los números reales .
