Aprendizaje Ockham

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

La aprendibilidad de Ockham implica aprendibilidad de 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 Ockham.

Introducción

El aprendizaje Ockham debe su nombre a la navaja de Ockham, un principio según el cual, en igualdad de condiciones, una explicación más corta de los datos observados debería ser preferible a una explicación más larga. 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 Ockham

La concisión de un concepto $c$ en la clase de concepto ${\mathcal {C}}$ puede expresarse mediante la longitud $size(c)$ de la cadena de bits más corta que puede representar $c$ en ${\mathcal {C}}$ . El aprendizaje Ockham relaciona la concisión de los resultados de un algoritmo de aprendizaje con su capacidad de predicción sobre datos desconocidos.

Dejemos que ${\mathcal {C}}$ y ${\mathcal {H}}$ sean clases de conceptos que contienen conceptos objetivo e hipótesis, respectivamente. Entonces, para las constantes $\alpha \geq 0$ y $0\leq \beta <1$ , un algoritmo de aprendizaje $L$ es un algoritmo Ockham $(\alpha ,\beta )$ para ${\mathcal {C}}$ usando ${\mathcal {H}}$ dado un conjunto $S=\{x_{1},\dots ,x_{m}\}$ de $m$ muestras etiquetados según un concepto $c\in {\mathcal {C}}$ , $L$ genera una hipótesis $h\in {\mathcal {H}}$ de forma que:

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

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

La relación entre Ockham y el aprendizaje PAC

El aprendizaje de Ockham implica el aprendizaje de PAC, como muestra el siguiente teorema de Blumer, et al^[2]:

Teorema (el aprendizaje de Ockham implica el aprendizaje de PAC)

Dejemos $L$ sea un algoritmo Ockham $(\alpha ,\beta )$ eficiente para $C$ usando $H$ . Entonces existe allí una contante $a>0$ de forma que para cualquier $0<\epsilon ,\delta <1$ , para cualquier distribución ${\mathcal {D}}$ , dando:

$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)$ muestras extraídas de $D$ y etiquetados según un concepto $c\in {\mathcal {C}}$ de una extensión de $n$ bits cada uno, el algoritmo $L$ dará como resultado una hipótesis $h\in {\mathcal {H}}$ de forma que $error(h)\leq \epsilon$ tendrá una probabilidad de por lo menos $1-\delta$ .

Aquí, $error(h)$ es con respecto al concepto $c$ y distribución $D$ . Esto implica que el algoritmo $L$ es también un aprendiz de PAC para la clase de conceptos $C$ usando hipótesis clase $H$ .

Una formulación ligeramente más general es la siguiente:

Teorema (el aprendizaje de Ockham implica el aprendizaje PAC, versión cardinalidad)

Tenemos $0<\epsilon ,\delta <1$ . Dejemos que $L$ sea un algoritmo tal que, dando $m$ muestras extraída de una distribución fija pero desconocida ${\mathcal {D}}$ y etiquetadas según un concepto $c\in {\mathcal {C}}$ de longitud de $n$ bits cada uno, produce una hipótesis $h\in {\mathcal {H}}_{n,m}$ que es coherente con las muestras etiquetadas.

Entonces, existe una constante $b$ de forma que $\log |{\mathcal {H}}_{n,m}|\leq b\epsilon m-\log {\frac {1}{\delta }}$ , entonces $L$ garantiza la salida de una hipótesis $h\in {\mathcal {H}}_{n,m}$ de forma que $error(h)\leq \epsilon$ tiene una probabilidad de por lo menos $1-\delta$ .

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

Un concepto clase $C$ es polinómicamente cerrado bajo listas de excepciones si existe un algoritmo en tiempo polinómico $A$ de forma tal que, cuando se le da la representación de un concepto $c\in {\mathcal {C}}$ y una lista finita de $E$ excepciones genera una representación de un concepto $c'\in {\mathcal {C}}$ de forma que los conceptos $c$ y $c'$ coinciden excepto en el set $E$ .

Prueba de que el aprendizaje Ockham implica el aprendizaje de PAC

Primero probamos la versión de la cardinalidad. Llamamos hipótesis $h\in {\mathcal {H}}$ mala si resulta en $error(h)\geq \epsilon$ , donde nuevamente $error(h)$ es con respecto al concepto real $c$ y la distribución subyacente $D$ . La probabilidad de que un conjunto de muestras $S$ es consistente con $h$ es a lo mucho $(1-\epsilon )^{m}$ , por la independencia de las muestras. Por el límite de unión, la probabilidad de que exista una hipótesis mala en ${\mathcal {H}}_{n,m}$ es a lo mucho $|{\mathcal {H}}_{n,m}|(1-\epsilon )^{m}$ , que es menor que $\delta$ si resulta $\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 primero. Como tenemos el algoritmo de Ockham $(\alpha ,\beta )$ esto significa que cualquier hipótesis emitida por $L$ puede representarse como máximo por $(n\cdot size(c))^{\alpha }m^{\beta }$ bits, y por lo tanto, $\log |{\mathcal {H}}_{n,m}|\leq (n\cdot size(c))^{\alpha }m^{\beta }$ . Esto es menor a $O(\epsilon m)-\log {\frac {1}{\delta }}$ si establecemos $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)$ para una constante $a>0$ . Así, por el Teorema de la versión de la cardinalidad, $L$ dará como resultado una hipótesis coherente $h$ con una probabilidad de por lo menos $1-\delta$ . Con esto concluye la demostración del primer teorema anterior.

Mejora de la complejidad de las muestras para problemas comunes

Aunque el aprendizaje de Ockham y PAC son equivalentes, el marco de Ockham puede utilizarse para producir límites más ajustados en la complejidad muestral de problemas clásicos, incluyendo conjunciones,^[2] conjunciones con pocas variables relevantes,^[4] y listas de decisión.^[5]

Extensiones

Los algoritmos de Ockham también han demostrado tener éxito para el aprendizaje PAC en presencia de errores,^[6]^[7] conceptos probabilísticos,^[8] aprendizaje de funciones^[9] y ejemplos markovianos no independientes.^[10]

Véase también

Referencias

↑ ^a ^b Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K (1987). «Occam's razor». Information processing letters.
↑ ^a ^b ^c Kearns, Michael J.; Vazirani, Umesh (15 de agosto de 1994). An Introduction to Computational Learning Theory (en inglés). MIT Press. ISBN 978-0-262-11193-5. Consultado el 26 de junio de 2024.
↑ Board, R., & Pitt, L. (1990). «On the necessity of Occam algorithms.». In Proceedings of the twenty-second annual ACM symposium on Theory of computing.
↑ Haussler, D. (1988). «Quantifying inductive bias: AI learning algorithms and Valiant's learning framework». Artificial intelligence.
↑ Rivest, R. L. (1987). Learning decision lists. Machine learning.
↑ Angluin, D., & Laird, P. (1988). «Learning from noisy examples». Machine Learning,.
↑ Kearns, M., & Li, M. (1993). «Learning in the presence of malicious errors.». SIAM Journal on Computing.
↑ Kearns, M. J., & Schapire, R. E. (1990). «Efficient distribution-free learning of probabilistic concepts». In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on.
↑ Natarajan, B. K. (1993). «Occam's razor for functions.». In Proceedings of the sixth annual conference on Computational learning theory.
↑ Aldous, D., & Vazirani, U. (1990). «A Markovian extension of Valiant's learning model». In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium.

Datos: Q25048571

[:0-1] Blumer, A., Ehrenfeucht, A., Haussler, D., & Warmuth, M. K (1987). «Occam's razor». Information processing letters.

[:1-2] Kearns, Michael J.; Vazirani, Umesh (15 de agosto de 1994). An Introduction to Computational Learning Theory (en inglés). MIT Press. ISBN 978-0-262-11193-5. Consultado el 26 de junio de 2024.

[3] Board, R., & Pitt, L. (1990). «On the necessity of Occam algorithms.». In Proceedings of the twenty-second annual ACM symposium on Theory of computing.

[4] Haussler, D. (1988). «Quantifying inductive bias: AI learning algorithms and Valiant's learning framework». Artificial intelligence.

[5] Rivest, R. L. (1987). Learning decision lists. Machine learning.

[6] Angluin, D., & Laird, P. (1988). «Learning from noisy examples». Machine Learning,.

[7] Kearns, M., & Li, M. (1993). «Learning in the presence of malicious errors.». SIAM Journal on Computing.

[8] Kearns, M. J., & Schapire, R. E. (1990). «Efficient distribution-free learning of probabilistic concepts». In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium on.

[9] Natarajan, B. K. (1993). «Occam's razor for functions.». In Proceedings of the sixth annual conference on Computational learning theory.

[10] Aldous, D., & Vazirani, U. (1990). «A Markovian extension of Valiant's learning model». In Foundations of Computer Science, 1990. Proceedings., 31st Annual Symposium.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]