Aprendizaje de Occam

Modelo de aprendizaje algorítmico

En la teoría del aprendizaje computacional , el aprendizaje de Occam es un modelo de aprendizaje algorítmico en el que el objetivo del alumno es generar una representación sucinta de los datos de entrenamiento recibidos. Esto está estrechamente relacionado con el aprendizaje probablemente aproximadamente correcto (PAC) , en el que se evalúa al alumno en función de su capacidad predictiva de un conjunto de pruebas.

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

Introducción

El aprendizaje de Occam recibe su nombre de la navaja de Occam , que es un principio que establece que, en igualdad de condiciones, se debe preferir una explicación más breve de los datos observados a una explicación 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 .

Definición del aprendizaje de Occam

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

Sean y clases de conceptos que contienen conceptos objetivo e hipótesis respectivamente. Entonces, para las constantes y , un algoritmo de aprendizaje es un algoritmo -Occam para usar si y solo si, dado un conjunto de muestras etiquetadas de acuerdo con un concepto , genera una hipótesis tal que ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle \alpha \geq 0}$ ${\displaystyle 0\leq \beta <1}$ ${\displaystyle L}$ ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle S=\{x_{1},\dots ,x_{m}\}}$ ${\displaystyle m}$ ${\displaystyle c\in {\mathcal {C}}}$ ${\displaystyle L}$ ${\displaystyle h\in {\mathcal {H}}}$

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

donde es la longitud máxima de cualquier muestra . Un algoritmo de Occam se llama eficiente si se ejecuta en un polinomio de tiempo en , , y Decimos que una clase de concepto es aprendible de Occam con respecto a una clase de hipótesis si existe un algoritmo de Occam eficiente para usar ${\displaystyle n}$ ${\displaystyle x\in S}$ ${\displaystyle n}$ ${\displaystyle m}$ ${\displaystyle size(c).}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {H}}.}$

La relación entre Occam y el aprendizaje PAC

La capacidad de aprendizaje de Occam implica la capacidad de aprendizaje de PAC, como lo muestra el siguiente teorema de Blumer et al. ^[2] :

Teorema (El aprendizaje de Occam implica el aprendizaje de PAC)

Sea un algoritmo -Occam eficiente para usar . Entonces existe una constante tal que para cualquier , para cualquier distribución , dadas muestras extraídas de y etiquetadas de acuerdo con un concepto de longitud bits cada una, el algoritmo generará una hipótesis tal que con una probabilidad de al menos . ${\displaystyle L}$ ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {H}}}$ ${\displaystyle a>0}$ ${\displaystyle 0<\epsilon ,\delta <1}$ ${\displaystyle {\mathcal {D}}}$ ${\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)}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle c\in {\mathcal {C}}}$ ${\displaystyle n}$ ${\displaystyle L}$ ${\displaystyle h\in {\mathcal {H}}}$ ${\displaystyle error(h)\leq \epsilon }$ ${\displaystyle 1-\delta }$

Aquí, se refiere al concepto y la distribución . Esto implica que el algoritmo también es un aprendiz de PAC para la clase de concepto que utiliza la clase de hipótesis . Una formulación un poco más general es la siguiente: ${\displaystyle error(h)}$ ${\displaystyle c}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle L}$ ${\displaystyle {\mathcal {C}}}$ ${\displaystyle {\mathcal {H}}}$

Teorema (El aprendizaje de Occam implica aprendizaje PAC, versión de cardinalidad)

Sea . Sea un algoritmo tal que, dadas muestras extraídas de una distribución fija pero desconocida y etiquetadas según un concepto de longitud bits cada una, genere una hipótesis que es consistente con las muestras etiquetadas. Entonces, existe una constante tal que si , entonces se garantiza que genere una hipótesis tal que con una probabilidad de al menos . ${\displaystyle 0<\epsilon ,\delta <1}$ ${\displaystyle L}$ ${\displaystyle m}$ ${\displaystyle {\mathcal {D}}}$ ${\displaystyle c\in {\mathcal {C}}}$ ${\displaystyle n}$ ${\displaystyle h\in {\mathcal {H}}_{n,m}}$ ${\displaystyle b}$ ${\displaystyle \log |{\mathcal {H}}_{n,m}|\leq b\epsilon m-\log {\frac {1}{\delta }}}$ ${\displaystyle L}$ ${\displaystyle h\in {\mathcal {H}}_{n,m}}$ ${\displaystyle error(h)\leq \epsilon }$ ${\displaystyle 1-\delta }$

Si bien los teoremas anteriores muestran que el aprendizaje de Occam es suficiente para el aprendizaje de PAC, no dicen nada sobre la necesidad. Board y Pitt muestran que, para una amplia variedad de clases de conceptos, el aprendizaje de Occam es de hecho necesario para el aprendizaje de PAC. ^[3] Demostraron que para cualquier clase de concepto que sea polinomialmente cerrada bajo listas de excepciones, la capacidad de aprendizaje de PAC implica la existencia de un algoritmo de Occam para esa clase de concepto. Las clases de concepto que son polinomialmente cerradas bajo listas de excepciones incluyen fórmulas booleanas, circuitos, autómatas finitos deterministas , listas de decisiones, árboles de decisiones y otras clases de concepto definidas geométricamente.

Una clase de concepto está polinomialmente cerrada bajo listas de excepciones si existe un algoritmo de tiempo polinomial tal que, cuando se da la representación de un concepto y una lista finita de excepciones , genera una representación de un concepto tal que los conceptos y concuerdan excepto en el conjunto . ${\displaystyle {\mathcal {C}}}$ ${\displaystyle A}$ ${\displaystyle c\in {\mathcal {C}}}$ ${\displaystyle E}$ ${\displaystyle c'\in {\mathcal {C}}}$ ${\displaystyle c}$ ${\displaystyle c'}$ ${\displaystyle E}$

Prueba de que el aprendizaje de Occam implica el aprendizaje de PAC

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

Usando el segundo teorema, podemos probar el primer teorema. Ya que tenemos un algoritmo de Occam, esto significa que cualquier hipótesis generada por puede ser representada por como máximo bits, y por lo tanto . Esto es menor que si establecemos para alguna constante . Por lo tanto, por el Teorema de la versión de Cardinalidad, generará una hipótesis consistente con probabilidad de al menos . Esto concluye la prueba del primer teorema anterior. ${\displaystyle (\alpha ,\beta )}$ ${\displaystyle L}$ ${\displaystyle (n\cdot size(c))^{\alpha }m^{\beta }}$ ${\displaystyle \log |{\mathcal {H}}_{n,m}|\leq (n\cdot size(c))^{\alpha }m^{\beta }}$ ${\displaystyle O(\epsilon m)-\log {\frac {1}{\delta }}}$ ${\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)}$ ${\displaystyle a>0}$ ${\displaystyle L}$ ${\displaystyle h}$ ${\displaystyle 1-\delta }$

Mejorar la complejidad de las muestras para problemas comunes

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

Extensiones

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

Véase también

• Minimización de riesgos estructurales
• Teoría del aprendizaje computacional

Referencias

1. Blumer, A., Ehrenfeucht, A., Haussler, D. y Warmuth, MK (1987). La navaja de Occam . Cartas de procesamiento de información, 24(6), 377-380.
2. Kearns, MJ y Vazirani, UV (1994). Una introducción a la teoría del aprendizaje computacional, capítulo 2. MIT Press.
3. Board, R., & Pitt, L. (1990, abril). Sobre la necesidad de los algoritmos de Occam. En Actas del vigésimo segundo simposio anual de la ACM sobre teoría de la computación (pp. 54-63). ACM.
4. Haussler, D. (1988). Cuantificación del sesgo inductivo: algoritmos de aprendizaje de IA y el marco de aprendizaje de Valiant Archivado el 12 de abril de 2013 en Wayback Machine . Inteligencia artificial, 36(2), 177-221.
5. Rivest, RL (1987). Aprendizaje de listas de decisiones. Aprendizaje automático , 2(3), 229-246.
6. Angluin, D., y Laird, P. (1988). Aprendizaje a partir de ejemplos ruidosos. Machine Learning, 2(4), 343-370.
7. Kearns, M., y Li, M. (1993). Aprendizaje en presencia de errores maliciosos. SIAM Journal on Computing, 22(4), 807-837.
8. Kearns, MJ y Schapire, RE (1990, octubre). Aprendizaje eficiente sin distribución de conceptos probabilísticos . En Foundations of Computer Science, 1990. Actas, 31.º Simposio anual sobre (págs. 382-391). IEEE.
9. Natarajan, BK (1993, agosto). La navaja de Occam para funciones. En Actas de la sexta conferencia anual sobre teoría del aprendizaje computacional (pp. 370-376). ACM.
10. Aldous, D., y Vazirani, U. (1990, octubre). Una extensión markoviana del modelo de aprendizaje de Valiant . En Foundations of Computer Science, 1990. Actas, 31.º Simposio anual sobre (págs. 392-396). IEEE.

Lectura adicional

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