Probablemente un aprendizaje aproximadamente correcto.

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.

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.

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

Para las siguientes definiciones, se utilizarán dos ejemplos. El primero es el problema del reconocimiento de caracteres dado un conjunto de n{displaystyle n} bits encoding una imagen de valor binario. El otro ejemplo es el problema de encontrar un intervalo que clasificará correctamente los puntos dentro del intervalo como positivos y los puntos fuera del rango como negativos.

Vamos X{displaystyle X} ser un conjunto llamado lugar o la codificación de todas las muestras. En el problema de reconocimiento de caracteres, el espacio de instancia es X={}0,1}n{displaystyle #. En el problema de intervalo el espacio de instancia, X{displaystyle X}, es el conjunto de todos los intervalos atados en R{displaystyle mathbb {R}, donde R{displaystyle mathbb {R} denota el conjunto de todos los números reales.

A concepto es un subconjunto c⊂ ⊂ X{displaystyle csubset X}. Un concepto es el conjunto de todos los patrones de bits en X={}0,1}n{displaystyle # que codifica una imagen de la letra "P". Un concepto de ejemplo del segundo ejemplo es el conjunto de intervalos abiertos, {}()a,b)▪ ▪ 0≤ ≤ a≤ ≤ π π /2,π π ≤ ≤ b≤ ≤ 13}{displaystyle {(a,b)mid 0leq aleq pi /2,pi leq bleq {sqrt {13}}}}, cada uno de los cuales contiene sólo los puntos positivos. A clase de concepto C{displaystyle C} es una colección de conceptos sobre X{displaystyle X}. Este podría ser el conjunto de todos los subconjuntos de la matriz de bits que están esqueletoizados 4-conectados (la anchura de la fuente es 1).

Vamos EX()c,D){displaystyle EX(c,D)} ser un procedimiento que dibuja un ejemplo, x{displaystyle x}, utilizando una distribución de probabilidad D{displaystyle D} y da la etiqueta correcta c()x){displaystyle c(x)}, eso es 1 si x▪ ▪ c{displaystyle xin c} y 0 de lo contrario.

Ahora, dado <math alttext="{displaystyle 0<epsilondelta 0.ε ε ,δ δ .1{displaystyle 0 realizadasepsilondelta.<img alt="{displaystyle 0<epsilondelta , asumir que hay un algoritmo A{displaystyle A} y un polinomio p{displaystyle p} dentro 1/ε ε ,1/δ δ {displaystyle 1/epsilon1/delta } (y otros parámetros relevantes de la clase C{displaystyle C}) tal que, dada una muestra de tamaño p{displaystyle p} dibujado según EX()c,D){displaystyle EX(c,D)}, entonces, con probabilidad de al menos 1− − δ δ {displaystyle 1-delta }, A{displaystyle A} produce una hipótesis h▪ ▪ C{displaystyle hin C} que tiene un error promedio inferior o igual a ε ε {displaystyle epsilon } on X{displaystyle X} con la misma distribución D{displaystyle D}. Más aún si la declaración anterior para el algoritmo A{displaystyle A} es verdad para cada concepto c▪ ▪ C{displaystyle cin C} y para cada distribución D{displaystyle D} sobre X{displaystyle X}, y para todos <math alttext="{displaystyle 0<epsilondelta 0.ε ε ,δ δ .1{displaystyle 0 realizadasepsilondelta.<img alt="{displaystyle 0<epsilondelta entonces C{displaystyle C} es (eficientemente) PAC aprendido (o PAC sin distribución). También podemos decir que A{displaystyle A} es un algoritmo de aprendizaje PAC para C{displaystyle C}.

Equivalent

Bajo algunas condiciones de regularidad, estas condiciones son equivalentes:

1. La clase de concepto C es PAC aprendeble.
2. La dimensión VC de C es finito.
3. C es una clase Glivenko-Cantelli uniforme.
4. C es compresible en el sentido de Littlestone y Warmuth