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 alta probabilidad (la parte "probablemente"), la función seleccionada tenga un error de generalización bajo (la parte "aproximadamente correcta"). El alumno debe poder aprender el concepto dada cualquier relación de aproximación arbitraria, 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 alumno encuentre funciones eficientes (requisitos de tiempo y espacio acotados a un polinomio del tamaño del ejemplo), y el propio alumno debe implementar un procedimiento eficiente (que requiere un recuento de ejemplo acotado a un polinomio del tamaño del concepto, modificado por los límites de aproximación y probabilidad ).

Definiciones y terminología

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 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. ${\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 intervalos, 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 con 4 conexiones (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 dibuje un ejemplo, usando una distribución de probabilidad y proporcione la etiqueta correcta , es decir, 1 si y 0 en caso contrario. ${\displaystyle 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 una probabilidad de al menos , genera una hipótesis que tiene un error promedio menor o igual que on con la misma distribución . Además, si la afirmación anterior para el algoritmo es cierta para cada concepto y para cada distribución sobre , y para todos, entonces se puede aprender (eficientemente) PAC (o se puede aprender PAC sin distribución ). También podemos decir que es un algoritmo de aprendizaje de PAC para . ${\displaystyle 0<\epsilon ,\delta <1}$ ${\displaystyle A}$ ${\displaystyle p}$ ${\displaystyle 1/\epsilon ,1/\delta }$ ${\displaystyle C}$ ${\displaystyle p}$ ${\displaystyle 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 algunas condiciones de regularidad, estas condiciones son equivalentes: ^[3]

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

Ver también

• aprendizaje de occam
• Procesamiento de datos
• Tolerancia a errores (aprendizaje PAC)
• Complejidad de la muestra

Referencias

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

Otras lecturas

• M. Kearns, U. Vazirani. Una 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 de PAC. Legible mediante acceso abierto desde el editor.
• D. Haussler. Descripción general del marco de aprendizaje probablemente aproximadamente correcto (PAC). Una introducción al tema.
• L. Valiente. 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). "Relación entre la compresión de datos y la capacidad de aprendizaje" (PDF) . Archivado desde el original (PDF) el 9 de agosto de 2017.
• Morán, Shay; Yehudayoff, Amir (2015). "Muestras de esquemas de compresión para clases de VC". arXiv : 1503.06960 [cs.LG].

enlaces externos

• Explicación interactiva del aprendizaje PAC