Aprendizaje PAC

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 ${\displaystyle 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 ${\displaystyle 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 ${\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 concepto de ejemplo del segundo ejemplo es el conjunto de todo de los números entre ${\displaystyle \pi /2}$ y ${\displaystyle {\sqrt {10}}}$. Una clase de concepto ${\displaystyle C}$ es un conjunto de conceptos sobre ${\displaystyle 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 ${\displaystyle EX(c,D)}$ un procedimiento que dibuja un ejemplo, ${\displaystyle x}$, utilizando una distribución de probabilidad ${\displaystyle D}$ y da la etiqueta correcta ${\displaystyle c(x)}$ , es decir 1 si ${\displaystyle x\in c}$ y 0 en otro caso

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

Un algoritmo corre en tiempo ${\displaystyle t}$ si dibuja como máximo ${\displaystyle t}$ ejemplos y requiere como máximo ${\displaystyle 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 ${\displaystyle 1/\epsilon }$ y ${\displaystyle 1/\delta }$ longitud de instancia.

Bajo ciertas condiciones de regularidad estas tres condiciones son equivalentes:

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

• 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.