Hispanopedia Wiki
Articulo de referencia

Teoría del aprendizaje computacional

En ciencias de la computación , la teoría del aprendizaje computacional (o simplemente teoría del aprendizaje ) es un subcampo de la inteligencia artificial dedicado al estudio ...

Hispanopedia WikiContenido en espanolLectura gratuita

En ciencias de la computación , la teoría del aprendizaje computacional (o simplemente 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 . [ 1 ]

Descripción general

Los resultados teóricos en aprendizaje automático suelen centrarse en un tipo de aprendizaje inductivo conocido como aprendizaje supervisado . En el aprendizaje supervisado, se proporcionan muestras etiquetadas a un algoritmo . Por ejemplo, las muestras podrían ser descripciones de setas, con etiquetas que indican si son comestibles o no. El algoritmo utiliza estas muestras etiquetadas para crear un clasificador. Este clasificador asigna etiquetas a nuevas muestras, incluidas aquellas que no ha encontrado previamente. El objetivo del algoritmo de aprendizaje supervisado es optimizar las métricas de rendimiento, como minimizar los errores en las 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. [ 2 ] En la teoría del aprendizaje computacional, un cálculo se considera viable si se puede realizar en tiempo polinomial . [ 2 ] Existen dos tipos de resultados de complejidad temporal:

  • Resultados positivos : demuestran que cierta clase de funciones se puede aprender en tiempo polinomial. 
  • Resultados negativos : Demuestran que ciertas clases no se pueden aprender en tiempo polinomial. [ 3 ] 

Los resultados negativos a menudo se basan en suposiciones comúnmente aceptadas, pero aún no probadas, tales como:

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

Si bien su objetivo principal es comprender el aprendizaje de forma abstracta, la teoría del aprendizaje computacional ha propiciado el desarrollo de algoritmos prácticos. Por ejemplo, la teoría PAC inspiró el boosting , la teoría VC dio lugar a las máquinas de vectores de soporte y la inferencia bayesiana a las redes bayesianas .

Véase también

Referencias

  1. ↑ "ACL - Asociación para el Aprendizaje Computacional" .
  2. 1 2 Valiant, LG (1984). "Una teoría de lo aprendible" (PDF) . Communications of the ACM . 27 (11): 1134– 1142.
  3. ↑ Kearns, Michael; Vazirani, Umesh (15 de agosto de 1994). Introducción a la teoría del aprendizaje computacional . MIT Press. ISBN 978-0262111935.
  4. ↑ Dana Angluin (1976). Una aplicación de la teoría de la complejidad computacional al estudio de la inferencia inductiva (tesis doctoral). Universidad de California en Berkeley.
  5. ↑ D. Angluin (1978). "Sobre la complejidad de la inferencia mínima de conjuntos regulares" . Información y control . 39 (3): 337–350 .
  6. ↑ Valiant, Leslie (1984). "Una teoría de lo aprendible" (PDF) . Communications of the ACM . 27 (11): 1134– 1142. doi : 10.1145/1968.1972 . S2CID 12837541. Archivado del original (PDF) el 17 de mayo de 2019. Consultado el 24 de noviembre de 2022 . 
  7. ↑ Vapnik, V.; Chervonenkis, A. (1971). "Sobre la convergencia uniforme de las frecuencias relativas de los eventos a sus probabilidades" (PDF) . Theory of Probability and Its Applications . 16 (2): 264– 280. doi : 10.1137/1116025 .
  8. ↑ Solomonoff, Ray (marzo de 1964). "Una teoría formal de la inferencia inductiva, parte 1" . Information and Control . 7 (1): 1– 22. doi : 10.1016/S0019-9958(64)90223-2 .
  9. ↑ Solomonoff, Ray (1964). "Una teoría formal de la inferencia inductiva, parte 2". Information and Control . 7 (2): 224– 254. doi : 10.1016/S0019-9958(64)90131-7 .
  10. ↑ Gold, E. Mark (1967). "Identificación de idiomas en el límite" (PDF) . Information and Control . 10 (5): 447– 474. doi : 10.1016/S0019-9958(67)91165-5 .

Lecturas adicionales

En la sección de publicaciones importantes sobre aprendizaje automático se ofrece una descripción de algunas de estas publicaciones.

Encuestas

  • Angluin, D. 1992. Teoría del aprendizaje computacional: Panorama general y bibliografía seleccionada. En Actas del Vigésimo Cuarto Simposio Anual de la ACM sobre Teoría de la Computación (mayo de 1992), páginas  351–369. http://portal.acm.org/citation.cfm?id=129712.129746
  • D. Haussler. Aprendizaje probablemente aproximadamente correcto. En Actas de la AAAI-90 de la Octava Conferencia Nacional sobre Inteligencia Artificial, Boston, MA, páginas 1101-1108. Asociación Estadounidense para la Inteligencia Artificial, 1990. http://citeseer.ist.psu.edu/haussler90probably.html

Selección de características

  • A. Dhagat y L. Hellerstein, "Aprendizaje PAC con atributos irrelevantes", en 'Actas del Simposio IEEE sobre Fundamentos de la Informática', 1994. http://citeseer.ist.psu.edu/dhagat94pac.html

Aprendizaje óptimo de la notación O

  • Oded Goldreich , Dana Ron . Sobre algoritmos de aprendizaje universal . http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2224

Resultados negativos

  • M. Kearns y Leslie Valiant . 1989. Limitaciones criptográficas en el aprendizaje de fórmulas booleanas y autómatas finitos. En Actas del 21.er Simposio Anual de la ACM sobre Teoría de la Computación, páginas 433-444, Nueva York. ACM. http://citeseer.ist.psu.edu/kearns89cryptographic.html

Tolerancia a errores

  • Michael Kearns y Ming Li. Aprendizaje en presencia de errores maliciosos. SIAM Journal on Computing, 22(4):807–837, agosto de 1993. http://citeseer.ist.psu.edu/kearns93learning.html
  • Kearns, M. (1993). Aprendizaje eficiente tolerante al ruido a partir de consultas estadísticas. En Actas del Vigésimo Quinto Simposio Anual de la ACM sobre Teoría de la Computación, páginas 392–401. http://citeseer.ist.psu.edu/kearns93efficient.html

Equivalencia

  • D. Haussler, M. Kearns, N. Littlestone y M. Warmuth , Equivalencia de modelos para la aprendibilidad polinomial, Actas del 1er Taller ACM sobre Teoría del Aprendizaje Computacional, (1988) 42-55.
  • Pitt, L.; Warmuth, MK (1990). "Reducibilidad que preserva la predicción" . Journal of Computer and System Sciences . 41 (3): 430– 467. doi : 10.1016/0022-0000(90)90028-J .
  • Fundamentos de la inferencia bayesiana