Teoría del Aprendizaje Computacional

La teoría del aprendizaje computacional estudia qué conceptos pueden aprenderse eficientemente a partir de ejemplos, tratando el aprendizaje como un problema de complejidad computacional y de muestreo.

Definition

La teoría del aprendizaje computacional es el estudio de los recursos, en datos y computación, necesarios para aprender conceptos a partir de ejemplos; en el modelo probablemente aproximadamente correcto, una clase de conceptos es aprendible si un algoritmo puede, a partir de un número polinomial de muestras y en tiempo polinomial, generar una hipótesis que sea precisa con alta probabilidad.

Scope

Este tema abarca modelos formales de aprendibilidad: el modelo probablemente aproximadamente correcto (PAC) que pregunta cuándo un concepto puede aprenderse con alta precisión y alta probabilidad a partir de un número polinomial de ejemplos y computación, los modelos de límite de error y aprendizaje en línea, la aprendibilidad débil versus fuerte y el boosting, y las conexiones con la complejidad computacional. Aborda tanto la viabilidad estadística como algorítmica del aprendizaje.

Core questions

• ¿Qué clases de conceptos pueden aprenderse eficientemente a partir de ejemplos?
• ¿Cuántos datos y computación requiere el aprendizaje de un concepto?
• ¿Cuál es la relación entre la aprendibilidad débil y la fuerte?
• ¿Cómo se conecta la aprendibilidad con la complejidad computacional?

Key theories

Aprendizaje probablemente aproximadamente correcto

El modelo de Valiant define una clase de conceptos como aprendible cuando un algoritmo eficiente puede producir, con alta probabilidad, una hipótesis de bajo error a partir de un número polinomial de ejemplos, haciendo de la aprendibilidad una cuestión computacional precisa.

Aprendibilidad débil y boosting

Un resultado central muestra que cualquier clase aprendible ligeramente mejor que el azar es también fuertemente aprendible, lo que llevó directamente a los algoritmos de boosting que amplifican los aprendices débiles en otros precisos.

Límites estadísticos y computacionales

La aprendibilidad está limitada tanto por la complejidad de la muestra, ligada a las medidas de capacidad, como por la dureza computacional, por lo que algunas clases son estadísticamente aprendibles pero computacionalmente intratables.

Clinical relevance

La teoría del aprendizaje computacional proporciona la base formal de lo que los algoritmos de aprendizaje pueden y no pueden lograr, e inspiró directamente métodos prácticos, especialmente el boosting, que surgió de la pregunta de si los aprendices débiles podían combinarse en aprendices fuertes; enmarca el aprendizaje como una disciplina computacional rigurosa.

History

Valiant introdujo el modelo probablemente aproximadamente correcto en 1984, dando al aprendizaje una definición computacional precisa y fundando el campo. Trabajos posteriores establecieron caracterizaciones de la complejidad de la muestra, la equivalencia de la aprendibilidad débil y fuerte que motivó el boosting, y resultados de dureza que muestran los límites computacionales del aprendizaje.

Key figures

• Leslie Valiant
• Michael Kearns
• Robert Schapire

Seminal works

• valiant1984
• kearns1994
• vapnik1995

Frequently asked questions

¿Qué significa probablemente aproximadamente correcto?

Significa que, con alta probabilidad sobre la muestra aleatoria, el aprendiz produce una hipótesis que es aproximadamente correcta, es decir, tiene un pequeño error en datos futuros. La aprendibilidad requiere lograr esto a partir de un número de ejemplos y una cantidad de computación que crecen solo polinomialmente.

¿Cómo condujo la teoría del aprendizaje al boosting?

Los investigadores se preguntaron si un aprendiz solo ligeramente mejor que la adivinación aleatoria podría convertirse en uno altamente preciso. La prueba de que la aprendibilidad débil y fuerte son equivalentes fue constructiva, y esa construcción se convirtió en los algoritmos de boosting ampliamente utilizados en la práctica.