En la teoría del aprendizaje computacional , probablemente aproximadamente correcto ( PAC ) el aprendizaje es un marco para el análisis matemático de 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 proporció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 limitados a un polinomio del tamaño del ejemplo), y el alumno mismo debe implementar un procedimiento eficiente (que requiere un recuento de ejemplo limitado 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 con PAC, primero tenemos que introducir algo de 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 debits que codifican una imagen de valor binario. 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 ser 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 la instancia,, es el conjunto de todos los intervalos acotados en , dónde denota el conjunto de todos los números reales .
Un concepto es un subconjunto. Un concepto es el conjunto de todos los patrones de bits enque 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 en 4 conectados (el ancho de la fuente es 1).
Dejar ser un procedimiento que dé ejemplo, , usando una distribución de probabilidad y da la etiqueta correcta , eso es 1 si y 0 en caso contrario.
Ahora, dado , suponga que hay un algoritmo y un polinomio en (y otros parámetros relevantes de la clase ) tal que, dada una muestra de tamaño dibujado de acuerdo con , entonces, con probabilidad de al menos , genera una hipótesis que tiene un error promedio menor o igual a en con la misma distribución . Además, si la declaración anterior para el algoritmo es cierto para todos los conceptos y para cada distribución encima y para todos luego se puede aprender (eficientemente) con PAC (o se puede aprender con PAC sin distribución ). También podemos decir quees un algoritmo de aprendizaje PAC para.
Equivalencia
En algunas condiciones de regularidad, estas condiciones son equivalentes: [4]
- La clase de concepto C se puede aprender con PAC.
- La dimensión VC de C es finita.
- C es una clase uniforme de Glivenko-Cantelli . [ aclaración necesaria ]
- C es comprimible en el sentido de Littlestone y Warmuth
Ver también
Referencias
- ^ L. Valiente. Una teoria de lo aprendible. Comunicaciones de la ACM, 27, 1984.
- ^ Kearns y Vazirani, pág. 1-12,
- ^ Balas Kausik Natarajan, Machine Learning, A Theoretical Approach, Morgan Kaufmann Publishers, 1991
- ^ Blumer, Anselmo; Ehrenfeucht, Andrzej; David, Haussler; Manfred, Warmuth (octubre de 1989). "Capacidad de aprendizaje y la dimensión de Vapnik-Chervonenkis". Revista de la Asociación de Maquinaria Informática . 36 (4): 929–965. doi : 10.1145 / 76359.76371 . S2CID 1138467 .
https://users.soe.ucsc.edu/~manfred/pubs/lrnk-olivier.pdf
Moran, Shay; Yehudayoff, Amir (2015). "Esquemas de compresión de muestra para clases de VC". arXiv : 1503.06960 [ cs.LG ].
Otras lecturas
- 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 de PAC. Legible a través de acceso abierto del editor.
- D. Haussler. Descripción general del marco de aprendizaje probablemente aproximadamente correcto (PAC) . 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.