Teoría del aprendizaje computacional

En informática, la teoría del aprendizaje computacional (o simplemente la teoría del aprendizaje) es un subcampo de la inteligencia artificial dedicado al estudio del diseño y análisis de algoritmos de aprendizaje automático.

Descripción general

Los resultados teóricos del aprendizaje automático tratan principalmente de un tipo de aprendizaje inductivo llamado aprendizaje supervisado. En el aprendizaje supervisado, a un algoritmo se le dan muestras etiquetadas de alguna manera útil. Por ejemplo, las muestras podrían ser descripciones de hongos y las etiquetas podrían indicar si los hongos son comestibles o no. El algoritmo toma estas muestras previamente etiquetadas y las utiliza para inducir un clasificador. Este clasificador es una función que asigna etiquetas a las muestras, incluidas las muestras que el algoritmo no ha visto previamente. El objetivo del algoritmo de aprendizaje supervisado es optimizar alguna medida del rendimiento, como minimizar la cantidad de errores cometidos en nuevas muestras.

Además de los límites de rendimiento, la teoría del aprendizaje computacional estudia la complejidad temporal y la viabilidad del aprendizaje. En En la teoría del aprendizaje computacional, un cálculo se considera factible si se puede realizar en tiempo polinómico. Hay dos tipos de tiempo resultados de complejidad:

• Resultados positivos – Mostrando que una cierta clase de funciones es aprendida en el tiempo polinomio.
• Resultados negativos – Mostrando que ciertas clases no se pueden aprender en el tiempo polinomio.

Los resultados negativos a menudo se basan en suposiciones comúnmente creídas, pero aún no comprobadas, como:

• Computacional complejidad – P ل NP (el problema P versus NP);
• Criptografía – Existen funciones de un solo sentido.

Existen varios enfoques diferentes de la teoría del aprendizaje computacional basados en hacer diferentes suposiciones sobre los principios de inferencia utilizados para generalizar a partir de datos limitados. Esto incluye diferentes definiciones de probabilidad (ver probabilidad de frecuencia, probabilidad bayesiana) y diferentes supuestos sobre la generación de muestras. Los diferentes enfoques incluyen:

• Exact learning, proposed by Dana Angluin;
• Probablemente el aprendizaje correcto (aprendizaje del PAC), propuesto por Leslie Valiant;
• Teoría VC, propuesta por Vladimir Vapnik y Alexey Chervonenkis;
• Inferencia inductiva desarrollada por Ray Solomonoff;
• Teoría del aprendizaje algorítmico, del trabajo de E. Mark Gold;
• Aprendizaje automático en línea, del trabajo de Nick Littlestone.

Si bien su objetivo principal es comprender el aprendizaje de manera abstracta, la teoría del aprendizaje computacional ha llevado al desarrollo de algoritmos prácticos. Por ejemplo, la teoría PAC inspiró el impulso, la teoría VC condujo a las máquinas de vectores de soporte y la inferencia bayesiana condujo a las redes de creencias.