Teoría del aprendizaje algorítmico

La teoría del aprendizaje algorítmico es un marco matemático para analizar problemas y algoritmos de aprendizaje automático . Entre sus sinónimos se incluyen la teoría del aprendizaje formal y la inferencia inductiva algorítmica . La teoría del aprendizaje algorítmico se diferencia de la teoría del aprendizaje estadístico en que no utiliza supuestos 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 considerarse ramas de la teoría del aprendizaje computacional .

A diferencia de la teoría del aprendizaje estadístico y la mayoría de las teorías estadísticas en general, la teoría del aprendizaje algorítmico no presupone 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 están (relativamente) libres de ruido pero no son 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 debería converger a una hipótesis correcta en cada secuencia de datos posible que sea consistente con el espacio del problema. Esta es una versión no probabilística de la consistencia estadística , que también requiere la convergencia a un modelo correcto en el límite, pero permite que un algoritmo de aprendizaje falle en secuencias de datos con medida de probabilidad 0 .

La teoría del aprendizaje algorítmico investiga la capacidad de aprendizaje de las máquinas de Turing . Otros marcos teóricos consideran una clase de algoritmos de aprendizaje mucho más restringida que las máquinas de Turing; por ejemplo, algoritmos que calculan hipótesis más rápidamente, por ejemplo, en tiempo polinomial . Un ejemplo de este marco es probablemente el aprendizaje aproximadamente correcto .

El concepto fue introducido en el artículo fundamental de E. Mark Gold , « Identificación de lenguajes en el límite ». ^{[ 4 ]} El objetivo de la identificación de lenguajes es que una máquina que ejecuta un programa sea capaz de desarrollar otro programa mediante el cual se pueda probar cualquier oración dada para determinar si es «gramatical» o «agramatical». El lenguaje 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 conocida por el evaluador.

En el modelo de aprendizaje de Gold, el evaluador proporciona al aprendiz una oración de ejemplo en cada paso, y el aprendiz responde con una hipótesis , que es un programa sugerido para determinar la corrección gramatical. Se requiere que el evaluador incluya todas las oraciones posibles (gramaticales o no) en la lista, pero no se exige un orden específico. Se requiere que el aprendiz, en cada paso, formule la hipótesis correcta para todas las oraciones presentadas hasta el momento.

Se dice que un aprendiz puede "aprender un idioma en el límite" si existe un cierto número de pasos a partir del cual su hipótesis deja de cambiar. En ese punto, efectivamente 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 para cada oración. No se requiere que el aprendiz sepa cuándo ha alcanzado una hipótesis correcta; basta con que sea verdadera.

Gold demostró que cualquier lenguaje definido por un programa de máquina de Turing puede aprenderse, en el límite, mediante otra máquina Turing-completa utilizando la enumeración . Esto se logra probando sucesivamente todos los posibles programas de máquina de Turing hasta encontrar uno que sea correcto hasta el momento; este programa constituye la hipótesis para el paso actual. Finalmente, se alcanza el programa correcto, tras lo cual la hipótesis no vuelve a cambiar (aunque cabe destacar que el aprendiz desconoce que no será necesario modificarla).

Gold también demostró que si al aprendiz solo se le dan ejemplos positivos (es decir, solo aparecen oraciones gramaticales en la entrada, no oraciones agramaticales), entonces solo se puede garantizar que el idioma se aprenda en el límite si solo hay un número finito de oraciones posibles en el idioma (esto es posible si, por ejemplo, se sabe que las oraciones tienen una longitud limitada).

La identificación de lenguajes en el límite es un modelo altamente abstracto. No contempla las limitaciones de tiempo de ejecución ni de memoria del ordenador que pueden darse 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 potente, ya que, si se mantienen estas condiciones estrictas, permite el aprendizaje de cualquier programa que se sepa que es computable . Esto se debe a que se puede escribir un programa de máquina de Turing para imitar cualquier programa en cualquier lenguaje de programación convencional . Véase la tesis de Church-Turing .

Los teóricos del aprendizaje han investigado otros criterios de aprendizaje, ^{[ 5 ]} como los siguientes.

• Eficiencia : minimizar el número de puntos de datos necesarios antes de converger a una hipótesis correcta.
• Cambios de mentalidad : minimizar el número de cambios de hipótesis que ocurren antes de la convergencia. ^{[ 6 ]}

Los límites del cambio de opinión están estrechamente relacionados con los límites de error que se estudian en la teoría del aprendizaje estadístico . ^{[ 7 ]} Kevin Kelly ha sugerido que minimizar los cambios de opinión está estrechamente relacionado con elegir hipótesis lo más simples posible en el sentido de la navaja de Occam . ^{[ 8 ]}

Desde 1990, existe una Conferencia Internacional sobre Teoría del Aprendizaje Algorítmico (ALT) , llamada Taller en sus primeros años (1990-1997 ) . ^{[ 9 ]} Entre 1992 y 2016, las actas se publicaron en la serie LNCS . ^{[ 10 ]} A partir de 2017, se publican en Proceedings of Machine Learning Research. La 34.ª conferencia se celebrará en Singapur en febrero de 2023. ^{[ 11 ]} Los temas de la conferencia abarcan todo el aprendizaje automático teórico, incluyendo 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.

• epistemología formal
• Dimensión de exclusión de la muestra