Probablemente un aprendizaje aproximadamente correcto

Marco para el análisis matemático del aprendizaje automático

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

El modelo se amplió posteriormente 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 alumno encuentre funciones eficientes (requisitos de tiempo y espacio limitados a un polinomio del tamaño del ejemplo) y el propio alumno debe implementar un procedimiento eficiente (que requiere un recuento de ejemplos limitado a un polinomio del tamaño del concepto, modificado por los límites de aproximación y verosimilitud ).

Definiciones y terminología

Para poder dar una definición de algo que se puede aprender mediante PAC, primero tenemos que introducir algo de 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 bits que codifica 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. ${\displaystyle n}$

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 de intervalo, el espacio de instancia, , es el conjunto de todos los intervalos acotados en , donde denota el conjunto de todos los números reales . ${\displaystyle X}$ ${\displaystyle X=\{0,1\}^{n}}$ ${\displaystyle X}$ ${\displaystyle \mathbb {R} }$ ${\displaystyle \mathbb {R} }$

Un concepto es un subconjunto . Un concepto es el conjunto de todos los patrones de bits que codifican una imagen de la letra "P". Un concepto de ejemplo del segundo ejemplo es el conjunto de intervalos abiertos, , cada uno de los cuales contiene solo los puntos positivos. Una clase de concepto es una colección de conceptos sobre . 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). ${\displaystyle c\subset X}$ ${\displaystyle X=\{0,1\}^{n}}$ ${\displaystyle \{(a,b)\mid 0\leq a\leq \pi /2,\pi \leq b\leq {\sqrt {13}}\}}$ ${\displaystyle C}$ ${\displaystyle X}$

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

Ahora, dado , supongamos que hay un algoritmo y un polinomio en (y otros parámetros relevantes de la clase ) tales que, dada una muestra de tamaño extraída de acuerdo con , entonces, con probabilidad de al menos , da como resultado una hipótesis que tiene un error promedio menor o igual a en con la misma distribución . Además, si la afirmación anterior para el algoritmo es verdadera para cada concepto y para cada distribución sobre , y para todos , entonces es (eficientemente) PAC aprendible (o PAC aprendible sin distribución ). También podemos decir que es un algoritmo de aprendizaje PAC para . ${\displaystyle 0<\epsilon ,\delta <1}$ ${\displaystyle A}$ ${\displaystyle p}$ ${\displaystyle 1/\epsilon ,1/\delta }$ ${\displaystyle C}$ ${\displaystyle p}$ ${\displaystyle \operatorname {EX} (c,D)}$ ${\displaystyle 1-\delta }$ ${\displaystyle A}$ ${\displaystyle h\in C}$ ${\displaystyle \epsilon }$ ${\displaystyle X}$ ${\displaystyle D}$ ${\displaystyle A}$ ${\displaystyle c\in C}$ ${\displaystyle D}$ ${\displaystyle X}$ ${\displaystyle 0<\epsilon ,\delta <1}$ ${\displaystyle C}$ ${\displaystyle A}$ ${\displaystyle C}$

Equivalencia

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

1. El concepto de clase C se puede aprender mediante PAC.
2. La dimensión VC de C es finita.
3. C es una clase uniforme de Glivenko-Cantelli . ^{[ aclaración necesaria ]}
4. C es compresible en el sentido de Littlestone y Warmuth

Véase también

• Aprendizaje de Occam
• Minería de datos
• Tolerancia a errores (aprendizaje PAC)
• Complejidad de la muestra

Referencias

1. L. Valiant. Una teoría de lo aprendible. Comunicaciones de la ACM, 27, 1984.
2. Kearns y Vazirani, pág. 1-12,
3. Blumer, Anselm; Ehrenfeucht, Andrzej; David, Haussler; Manfred, Warmuth (octubre de 1989). "Capacidad de aprendizaje y la dimensión Vapnik-Chervonenkis". Revista de la Asociación de Maquinaria Computacional . 36 (4): 929–965. doi : 10.1145/76359.76371 . S2CID  1138467.

Lectura adicional

• 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 tratamiento detallado de la capacidad de aprendizaje del PAC. Se puede leer a través de acceso abierto desde el editor.
• 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 sostiene que el aprendizaje PAC describe cómo los organismos evolucionan y aprenden.
• Littlestone, N.; Warmuth, MK (10 de junio de 1986). "Relating Data Compression and Learnability" (PDF) . Archivado desde el original (PDF) el 2017-08-09.
• Moran, Shay; Yehudayoff, Amir (2015). "Ejemplos de esquemas de compresión para clases VC". arXiv : 1503.06960 [cs.LG].

Enlaces externos

• Explicación interactiva del aprendizaje del PAC