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
[editar]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
[editar]La concisión de un concepto en la clase de concepto puede expresarse mediante la longitud de la cadena de bits más corta que puede representar en . 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 y sean clases de conceptos que contienen conceptos objetivo e hipótesis, respectivamente. Entonces, para las constantes y , un algoritmo de aprendizaje es un algoritmo Ockham para usando dado un conjunto de muestras etiquetados según un concepto , genera una hipótesis de forma que:
Donde es la longitud máxima de cualquier muestra . Un algoritmo de Ockham se denomina eficiente si se ejecuta en tiempo polinomial en , y Decimos una clase de concepto es aprendizaje de Ockham con respecto a una hipótesis de clase si existe un algoritmo Ockham eficiente para usando
La relación entre Ockham y el aprendizaje PAC
[editar]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)
[editar]Dejemos sea un algoritmo Ockham eficiente para usando . Entonces existe allí una contante de forma que para cualquier , para cualquier distribución , dando:
muestras extraídas de y etiquetados según un concepto de una extensión de bits cada uno, el algoritmo dará como resultado una hipótesis de forma que tendrá una probabilidad de por lo menos .
Aquí, es con respecto al concepto y distribución . Esto implica que el algoritmo es también un aprendiz de PAC para la clase de conceptos usando hipótesis clase .
Una formulación ligeramente más general es la siguiente:
Teorema (el aprendizaje de Ockham implica el aprendizaje PAC, versión cardinalidad)
[editar]Tenemos . Dejemos que sea un algoritmo tal que, dando muestras extraída de una distribución fija pero desconocida y etiquetadas según un concepto de longitud de bits cada uno, produce una hipótesis que es coherente con las muestras etiquetadas.
Entonces, existe una constante de forma que , entonces garantiza la salida de una hipótesis de forma que tiene una probabilidad de por lo menos .
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 es polinómicamente cerrado bajo listas de excepciones si existe un algoritmo en tiempo polinómico de forma tal que, cuando se le da la representación de un concepto y una lista finita de excepciones genera una representación de un concepto de forma que los conceptos y coinciden excepto en el set .
Prueba de que el aprendizaje Ockham implica el aprendizaje de PAC
[editar]Primero probamos la versión de la cardinalidad. Llamamos hipótesis mala si resulta en , donde nuevamente es con respecto al concepto real y la distribución subyacente . La probabilidad de que un conjunto de muestras es consistente con es a lo mucho , por la independencia de las muestras. Por el límite de unión, la probabilidad de que exista una hipótesis mala en es a lo mucho , que es menor que si resulta . Con esto concluye la demostración del segundo teorema anterior.
Utilizando el segundo teorema, podemos demostrar el primero. Como tenemos el algoritmo de Ockham esto significa que cualquier hipótesis emitida por puede representarse como máximo por bits, y por lo tanto, . Esto es menor a si establecemos para una constante . Así, por el Teorema de la versión de la cardinalidad, dará como resultado una hipótesis coherente con una probabilidad de por lo menos . Con esto concluye la demostración del primer teorema anterior.
Mejora de la complejidad de las muestras para problemas comunes
[editar]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
[editar]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
[editar]Referencias
[editar]- ↑ 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.