Probablemente un 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 aprendiz recibe muestras y debe seleccionar una función de generalización (denominada hipótesis ) de una clase determinada de funciones posibles. El objetivo es que, con alta probabilidad (la parte "probablemente"), la función seleccionada tenga un bajo error de generalización (la parte "aproximadamente correcta"). El aprendiz debe ser capaz de aprender el concepto dada cualquier razón de aproximación, probabilidad de éxito o distribución de las muestras .

Posteriormente, el modelo se amplió para tratar el ruido (muestras mal clasificadas).

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 algoritmo de aprendizaje encuentre funciones eficientes (con requisitos de tiempo y espacio limitados por un polinomio del tamaño del ejemplo), y que el propio algoritmo implemente un procedimiento eficiente (que requiera un número de ejemplos limitado por 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 mediante PAC, primero tenemos que introducir cierta terminología. ^{[ 2 ]}

Para las siguientes definiciones, se utilizarán dos ejemplos. El primero es el problema del reconocimiento de caracteres dado un conjunto de${\displaystyle n}$bits que codifican una imagen binaria. 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.

Dejar${\displaystyle X}$ser un conjunto llamado espacio de instancias o la codificación de todas las muestras. En el problema de reconocimiento de caracteres, el espacio de instancias es${\displaystyle X=\{0,1\}^{n}}$. En el problema de intervalos el espacio de instancias,${\displaystyle X}$, es el conjunto de todos los intervalos acotados en${\displaystyle \mathbb {R} }$, dónde${\displaystyle \mathbb {R} }$denota el conjunto de todos los números reales .

Un concepto es un subconjunto${\displaystyle c\subset X}$. Un concepto es el conjunto de todos los patrones de bits en${\displaystyle X=\{0,1\}^{n}}$que codifican una imagen de la letra "P". Un ejemplo de concepto del segundo ejemplo es el conjunto de intervalos abiertos,${\displaystyle \{(a,b)\mid 0\leq a\leq \pi /2,\pi \leq b\leq {\sqrt {13}}\}}$, cada uno de los cuales contiene solo los puntos positivos. Una clase de concepto${\displaystyle C}$es una colección de conceptos más${\displaystyle X}$. Este podría ser el conjunto de todos los subconjuntos de la matriz de bits que están esqueletizados 4-conectados (el ancho de la fuente es 1).

Dejar${\displaystyle \operatorname {EX} (c,D)}$ser un procedimiento que sirva de ejemplo,${\displaystyle x}$, utilizando una distribución de probabilidad${\displaystyle D}$y proporciona la etiqueta correcta${\displaystyle c(x)}$, es decir, 1 si${\displaystyle x\in c}$y 0 en caso contrario.

Ahora, dado${\displaystyle 0<\épsilon,\delta <1}$Supongamos que existe un algoritmo${\displaystyle A}$y un polinomio${\displaystyle p}$en${\displaystyle 1/\épsilon,1/\delta}$(y otros parámetros relevantes de la clase${\displaystyle C}$) de tal manera que, dada una muestra de tamaño${\displaystyle p}$dibujado según${\displaystyle \operatorname {EX} (c,D)}$, entonces, con una probabilidad de al menos${\displaystyle 1-\delta }$,${\displaystyle A}$genera una hipótesis${\displaystyle h\in C}$que tiene un error promedio menor o igual a${\displaystyle \epsilon }$en${\displaystyle X}$con la misma distribución${\displaystyle D}$Además, si la afirmación anterior para el algoritmo${\displaystyle A}$Esto es cierto para cada concepto.${\displaystyle c\in C}$y por cada distribución${\displaystyle D}$encima${\displaystyle X}$y para todos${\displaystyle 0<\épsilon,\delta <1}$ entonces${\displaystyle C}$es (eficientemente) aprendible mediante PAC (o aprendible mediante PAC sin distribución ). También podemos decir que${\displaystyle A}$es un algoritmo de aprendizaje PAC para${\displaystyle C}$.

Bajo ciertas condiciones de regularidad, estas condiciones son equivalentes: ^{[ 3 ]}

1. La clase de concepto C es aprendible mediante PAC.
2. La dimensión VC de C es finita.
3. C es una clase uniformemente Glivenko-Cantelli .
4. C es compresible en el sentido de Littlestone y Warmuth.

• minería de datos
• Tolerancia al error (aprendizaje PAC)
• Aprendizaje de Occam
• Complejidad de la muestra

• M. Kearns, U. Vazirani. Introducción a la teoría del aprendizaje computacional . MIT Press, 1994. Un libro de texto.
• M. Mohri, A. Rostamizadeh y A. Talwalkar. Fundamentos del aprendizaje automático . MIT Press, 2018. El capítulo 2 contiene un análisis detallado de la capacidad de aprendizaje PAC. Disponible en acceso abierto a través de la editorial.
• D. Haussler. Descripción general del marco de aprendizaje Probablemente Aproximadamente Correcto (PAC) . Una introducción al tema.
• L. Valiant. Probablemente aproximadamente correcto. Basic Books, 2013. En el que Valiant argumenta que el aprendizaje PAC describe cómo evolucionan y aprenden los organismos.
• Littlestone, N.; Warmuth, MK (10 de junio de 1986). "Relación entre compresión de datos y capacidad de aprendizaje" (PDF) . Archivado del original (PDF) el 9 de agosto de 2017.
• Moran, Shay; Yehudayoff, Amir (2015). "Esquemas de compresión de muestras para clases VC". arXiv : 1503.06960 [ cs.LG ].

• Explicación interactiva del aprendizaje PAC