La teoría del aprendizaje algorítmico es un marco matemático para analizar problemas y algoritmos de aprendizaje automático . Los sinónimos incluyen teoría del aprendizaje formal e inferencia inductiva algorítmica [ cita requerida ] . La teoría del aprendizaje algorítmico se diferencia de la teoría del aprendizaje estadístico en que no utiliza suposiciones ni análisis estadísticos. Tanto la teoría del aprendizaje algorítmico como la estadística se ocupan del aprendizaje automático y, por lo tanto, pueden verse como ramas de la teoría del aprendizaje computacional [ cita requerida ] .
A diferencia de la teoría del aprendizaje estadístico y de la mayoría de las teorías estadísticas en general, la teoría del aprendizaje algorítmico no supone que los datos sean muestras aleatorias, es decir, que los puntos de datos sean independientes entre sí. Esto hace que la teoría sea adecuada para dominios donde las observaciones son (relativamente) libres de ruido pero no aleatorias, como el aprendizaje de idiomas [1] y el descubrimiento científico automatizado. [2] [3]
El concepto fundamental de la teoría del aprendizaje algorítmico es el aprendizaje en el límite: a medida que aumenta el número de puntos de datos, un algoritmo de aprendizaje debe converger hacia una hipótesis correcta en cada secuencia de datos posible consistente con el espacio del problema. Esta es una versión no probabilística de consistencia estadística , que también requiere convergencia a un modelo correcto en el límite, pero permite al alumno fallar en secuencias de datos con medida de probabilidad 0 [ cita necesaria ] .
La teoría del aprendizaje algorítmico investiga el poder de aprendizaje de las máquinas de Turing . Otros marcos consideran una clase mucho más restringida de algoritmos de aprendizaje que las máquinas de Turing, por ejemplo, aprendices que calculan hipótesis más rápidamente, por ejemplo en tiempo polinomial . Un ejemplo de tal marco es probablemente el aprendizaje aproximadamente correcto [ cita requerida ] .
El concepto fue introducido en el artículo fundamental de E. Mark Gold " Identificación del lenguaje en el límite ". [4] El objetivo de la identificación del lenguaje es que una máquina que ejecuta un programa sea capaz de desarrollar otro programa mediante el cual se pueda probar cualquier oración determinada para determinar si es "gramatical" o "agramatical". El idioma que se aprende no tiene por qué ser inglés ni ningún otro idioma natural ; de hecho, la definición de "gramatical" puede ser absolutamente cualquier cosa que el evaluador conozca.
En el modelo de aprendizaje de Gold, el evaluador le da al alumno una oración de ejemplo en cada paso, y el alumno responde con una hipótesis , que es un programa sugerido para determinar la corrección gramatical. Se requiere del evaluador que todas las oraciones posibles (gramaticales o no) aparezcan eventualmente en la lista, pero no se requiere ningún orden en particular. Se requiere que el alumno en cada paso la hipótesis sea correcta para todas las oraciones hasta el momento. [ cita necesaria ]
Se dice que un estudiante en particular es capaz de "aprender un idioma hasta el límite" si hay un cierto número de pasos más allá del cual su hipótesis ya no cambia. [ cita necesaria ] En este punto, de hecho ha aprendido el idioma, porque cada oración posible aparece en algún lugar de la secuencia de entradas (pasadas o futuras), y la hipótesis es correcta para todas las entradas (pasadas o futuras), por lo que la hipótesis es correcta. por cada frase. No se requiere que el alumno sea capaz de decir cuándo ha llegado a una hipótesis correcta, todo lo que se requiere es que sea cierta.
Gold demostró que cualquier lenguaje definido por un programa de máquina de Turing puede ser aprendido en el límite por otra máquina de Turing completa mediante enumeración . [ se necesita aclaración ] Esto lo hace el alumno probando todos los programas posibles de la máquina de Turing por turno hasta encontrar uno que sea correcto hasta el momento; esto forma la hipótesis para el paso actual. Con el tiempo, se alcanzará el programa correcto, después del cual la hipótesis nunca volverá a cambiar (pero tenga en cuenta que el alumno no sabe que no será necesario cambiar).
Gold también demostró que si al alumno se le dan solo ejemplos positivos (es decir, solo aparecen oraciones gramaticales en la entrada, no oraciones agramaticales), entonces solo se puede garantizar que el idioma se aprenderá en el límite si solo hay un número finito de ejemplos. posibles oraciones en el idioma (esto es posible si, por ejemplo, se sabe que las oraciones tienen una longitud limitada). [ se necesita aclaración ]
La identificación del lenguaje en el límite es un modelo muy abstracto. No permite límites de tiempo de ejecución o memoria de computadora que pueden ocurrir en la práctica, y el método de enumeración puede fallar si hay errores en la entrada. Sin embargo, el marco es muy poderoso, porque si se mantienen estas condiciones estrictas, permite el aprendizaje de cualquier programa que se sepa que es computable [ cita necesaria ] . Esto se debe a que un programa de máquina de Turing puede escribirse para imitar cualquier programa en cualquier lenguaje de programación convencional . Véase tesis de Church-Turing .
Los teóricos del aprendizaje han investigado otros criterios de aprendizaje, [5] como los siguientes.
Los límites de cambio de mente están estrechamente relacionados con los límites de error que se estudian en la teoría estadística del aprendizaje . [7] Kevin Kelly ha sugerido que minimizar los cambios mentales está estrechamente relacionado con elegir hipótesis máximamente simples en el sentido de la navaja de Occam . [8]
Desde 1990, existe una Conferencia Internacional sobre Teoría del Aprendizaje Algorítmico (ALT) , denominada Taller en sus primeros años (1990–1997). [9] Entre 1992 y 2016, se publicaron actas en la serie LNCS . [10] A partir de 2017, se publican en Proceedings of Machine Learning Research. La 34ª conferencia se llevará a cabo en Singapur en febrero de 2023. [11] Los temas de la conferencia cubren todo el aprendizaje automático teórico, incluida la teoría del aprendizaje estadístico y computacional, el aprendizaje en línea, el aprendizaje activo, el aprendizaje por refuerzo y el aprendizaje profundo.