Aprendizaje de Occam

En la teoría del aprendizaje computacional , el aprendizaje de Occam es un modelo de aprendizaje algorítmico cuyo objetivo es generar una representación concisa de los datos de entrenamiento recibidos. Esto guarda estrecha relación con el aprendizaje probablemente aproximadamente correcto (PAC) , donde el algoritmo se evalúa en función de su capacidad predictiva sobre un conjunto de prueba.

La capacidad de aprendizaje de Occam implica el aprendizaje PAC, y para una amplia variedad de clases de conceptos , lo contrario también es cierto: la capacidad de aprendizaje PAC implica la capacidad de aprendizaje de Occam.

El aprendizaje de Occam recibe su nombre de la navaja de Occam , un principio que establece que, en igualdad de condiciones, se debe preferir una explicación más breve de los datos observados a una más extensa. La teoría del aprendizaje de Occam es una justificación formal y matemática de este principio. Blumer et al. ^{[ 1 ]} demostraron por primera vez que el aprendizaje de Occam implica el aprendizaje PAC, que es el modelo estándar de aprendizaje en la teoría del aprendizaje computacional. En otras palabras, la parsimonia (de la hipótesis de salida) implica poder predictivo .

La concisión de un concepto${\displaystyle c}$en la clase conceptual${\displaystyle {\mathcal {C}}}$se puede expresar mediante la longitud${\displaystyle size(c)}$de la cadena de bits más corta que puede representar${\displaystyle c}$en${\displaystyle {\mathcal {C}}}$El aprendizaje de Occam relaciona la concisión del resultado de un algoritmo de aprendizaje con su poder predictivo sobre datos no vistos.

Dejar${\displaystyle {\mathcal {C}}}$y${\displaystyle {\mathcal {H}}}$sean clases de conceptos que contengan conceptos objetivo e hipótesis respectivamente. Entonces, para constantes${\displaystyle \alpha \geq 0}$y${\displaystyle 0\leq \beta <1}$, un algoritmo de aprendizaje${\displaystyle L}$es un${\displaystyle (\alpha,\beta)}$-Algoritmo de Occam para${\displaystyle {\mathcal {C}}}$usando${\displaystyle {\mathcal {H}}}$si y solo si, dado un conjunto${\displaystyle S=\{x_{1},\dots ,x_{m}\}}$de${\displaystyle m}$muestras etiquetadas según un concepto${\displaystyle c\in {\mathcal {C}}}$,${\displaystyle L}$genera una hipótesis${\displaystyle h\in {\mathcal {H}}}$de tal manera que

• ${\displaystyle h}$es consistente con${\displaystyle c}$en${\displaystyle S}$(eso es,${\displaystyle h(x)=c(x),\forall x\in S}$), y
• ${\displaystyle size(h)\leq (n\cdot size(c))^{\alpha }m^{\beta }}$^{[ 2 ] [ 1 ]}

dónde${\displaystyle n}$es la longitud máxima de cualquier muestra${\displaystyle x\in S}$Un algoritmo de Occam se denomina eficiente si se ejecuta en tiempo polinomial en${\displaystyle n}$,${\displaystyle m}$, y${\displaystyle size(c).}$Decimos una clase de concepto${\displaystyle {\mathcal {C}}}$¿Es Occam aprendible con respecto a una clase de hipótesis?${\displaystyle {\mathcal {H}}}$si existe un algoritmo de Occam eficiente para ${\displaystyle {\mathcal {C}}}$usando${\displaystyle {\mathcal {H}}.}$

La aprendibilidad de Occam implica la aprendibilidad PAC, como lo demuestra el siguiente teorema de Blumer, et al. ^{[ 2 ]} :

Primero demostramos la versión de cardinalidad. Llamemos hipótesis${\displaystyle h\in {\mathcal {H}}}$malo si${\displaystyle error(h)\geq \epsilon }$, donde de nuevo${\displaystyle error(h)}$es con respecto al concepto verdadero${\displaystyle c}$y la distribución subyacente${\displaystyle {\mathcal {D}}}$. La probabilidad de que un conjunto de muestras${\displaystyle S}$es consistente con${\displaystyle h}$es como máximo${\displaystyle (1-\epsilon )^{m}}$, por la independencia de las muestras. Por el límite de unión, la probabilidad de que exista una mala hipótesis en${\displaystyle {\mathcal {H}}_{n,m}}$es como máximo${\displaystyle |{\mathcal {H}}_{n,m}|(1-\epsilon )^{m}}$, que es menos que${\displaystyle \delta }$si${\displaystyle \log |{\mathcal {H}}_{n,m}|\leq O(\epsilon m)-\log {\frac {1}{\delta }}}$. Con esto concluye la demostración del segundo teorema anterior.

Utilizando el segundo teorema, podemos demostrar el primer teorema. Dado que tenemos un${\displaystyle (\alpha,\beta)}$-Algoritmo de Occam, esto significa que cualquier hipótesis producida por${\displaystyle L}$puede representarse mediante como máximo${\displaystyle (n\cdot size(c))^{\alpha }m^{\beta }}$bits, y por lo tanto${\displaystyle \log |{\mathcal {H}}_{n,m}|\leq (n\cdot size(c))^{\alpha }m^{\beta }}$Esto es menos que${\displaystyle O(\epsilon m)-\log {\frac {1}{\delta }}}$si establecemos${\displaystyle m\geq a\left({\frac {1}{\epsilon }}\log {\frac {1}{\delta }}+\left({\frac {(n\cdot size(c))^{\alpha })}{\epsilon }}\right)^{\frac {1}{1-\beta }}\right)}$por alguna constante${\displaystyle a>0}$. Por lo tanto, según el Teorema de la versión de cardinalidad,${\displaystyle L}$generará una hipótesis consistente${\displaystyle h}$con probabilidad al menos${\displaystyle 1-\delta }$. Con esto concluye la demostración del primer teorema anterior.

Aunque la capacidad de aprendizaje de Occam y PAC son equivalentes, el marco de Occam se puede utilizar para producir límites más ajustados en la complejidad de la muestra de problemas clásicos, incluidas las conjunciones, ^{[ 2 ]} las conjunciones con pocas variables relevantes, ^{[ 4 ]} y las listas de decisiones. ^{[ 5 ]}

También se ha demostrado que los algoritmos de Occam son exitosos para el aprendizaje PAC en presencia de errores, ^{[ 6 ] [ 7 ]} conceptos probabilísticos, ^{[ 8 ]} aprendizaje de funciones ^{[ 9 ]} y ejemplos no independientes markovianos. ^{[ 10 ]}

• Teoría del aprendizaje computacional
• Minimización del riesgo estructural

• Blumer, A.; Ehrenfeucht, A.; Haussler, D.; Warmuth, MK . Aprendizaje y la dimensión de Vapnik-Chervonenkis . Journal of the ACM, 36(4):929–865, 1989.