Aprendizaje PAC

En teoría de aprendizaje computacional, el aprendizaje correcto probablemente aproximado (Aprendizaje PAC) (en inglés probably approximately correct learning) es un marco para el análisis matemático de aprendizaje de máquina. Este fue propuesto en 1984 por Leslie Valiant.^[1]

En este marco, la técnica de aprendizaje recibe muestras y debe seleccionar una función de generalización (llamado la hipótesis) de cierta clase de funciones posibles. El objetivo es que, con una alta probabilidad (la parte del "probablemente"), la función seleccionada tenga un error de generalización bajo (la parte del "correcto aproximado"). La técnica de aprendizaje tiene que ser capaz de aprender el concepto dada cualquier proporción de aproximación arbitraria, probabilidad de éxito, o distribución de las muestras.

El modelo fue más tarde extendido para tratar ruido (muestras mal clasificadas).

Una innovación importante al marco del PAC es la introducción de los conceptos de la teoría de la complejidad computacional de aprendizaje automático. En particular, se espera que la técnica de aprendizaje encuentre funciones eficientes (en tiempo y requisitos espaciales limitados a un polinomio del tamaño del ejemplo), y la técnica de aprendizaje en sí debe implementar un procedimiento eficiente (que exige un recuento limitado a un polinomio de la medida del concepto, modificado por los límites de aproximación y de probabilidad).

Definiciones y terminología

Con el fin de dar a la definición de algo que es Aprendizaje PAC, primero tenemos que introducir algunas terminologías.^[2]^[3]

Para las siguientes definiciones, se usarán dos ejemplos. El primero es el problema de reconocimiento de caracteres dado una matriz de $n$ bits que codifican una imagen binaria-valor. El otro ejemplo es el problema de encontrar un intervalo que clasificará correctamente los puntos dentro del intervalo como positivo y los puntos exteriores al rango como negativo.

Sea X un conjunto llamado el espacio de instancia o la codificación de todas las muestras, y cada instancia tiene la longitud asignada. En el problema de reconocimiento del caracteres, el espacio de instancia es $X=\{0,1\}^{n}$ . En el problema de intervalo el espacio de instancia es X = R , dónde R denota el conjunto de todos los números reales.

Un concepto es un subconjunto $c\subset X$ . Un concepto es el conjunto de todos los patrones de bits en $X=\{0,1\}^{n}$ que codifican una imagen de la letra "P". Un concepto de ejemplo del segundo ejemplo es el conjunto de todo de los números entre $\pi /2$ y ${\sqrt {10}}$ . Una clase de concepto $C$ es un conjunto de conceptos sobre $X$ . Esto podría ser el conjunto de todos los subconjuntos de la matriz de bits que son esqueletizados 4-conectados (ancho de la fuente es 1).

Siendo $EX(c,D)$ un procedimiento que dibuja un ejemplo, $x$ , utilizando una distribución de probabilidad $D$ y da la etiqueta correcta $c(x)$ , es decir 1 si $x\in c$ y 0 en otro caso

Digamos que hay un algoritmo $A$ que da acceso a la $EX(c,D)$ y entradas $\epsilon$ y $\delta$ que, con probabilidad de al menos $1-\delta$ , $A$ produce una hipótesis $h\in C$ que tiene de media errores menores o igual a $\epsilon$ con los ejemplos extraídos de $X$ con la distribución $D$ . Si hay tal algoritmo para cada concepto $c\in C$ , para cada distribución $D$ sobre $X$ , y siempre se cumple que $0<\epsilon <1/2$ y $0<\delta <1/2$ entonces $C$ es aprendizaje PAC. También podemos decir que $A$ es un algoritmo PAC de aprendizaje para $C$ .

Un algoritmo corre en tiempo $t$ si dibuja como máximo $t$ ejemplos y requiere como máximo $t$ pasos de tiempo. Una clase concepto es aprendizaje PAC eficiente si es PAC aprendible por un algoritmo que se ejecuta en tiempo polinomial en $1/\epsilon$ y $1/\delta$ longitud de instancia.

Equivalencia

Bajo ciertas condiciones de regularidad estas tres condiciones son equivalentes:

La clase de concepto C es PAC aprendible.
La dimensión VC de C es finito.
C es una clase Glivenko-Cantelli uniforme

Referencias

↑ L. Valiant.
↑ Kearns and Vazirani, pg. 1-12,
↑ Balas Kausik Natarajan, Machine Learning , A Theoretical Approach, Morgan Kaufmann Publishers, 1991

Lectura adicional

M. Kearns, U. Vazirani. Una Introducción a Teoría de Aprendizaje Computacional. MIT Prensa, 1994. Un textbook.
D. Haussler. Visión general del Probablemente Aproximadamente Corregir (PAC) Marco de Aprendizaje. Una introducción al tema.
L. Valiant. Probablemente Aproximadamente Correcto. Libros básicos, 2013. En qué Valiant argumenta que PAC el aprendizaje describe qué los organismos evolucionan y aprender.

Datos: Q458526

[valiant-1] L. Valiant.

[2] Kearns and Vazirani, pg. 1-12,

[3] Balas Kausik Natarajan, Machine Learning , A Theoretical Approach, Morgan Kaufmann Publishers, 1991

[1]

[2]

[3]