Teoría del aprendizaje computacional

Teoría del aprendizaje automático

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

Descripción general

Los resultados teóricos en el aprendizaje automático tratan principalmente de un tipo de aprendizaje inductivo llamado aprendizaje supervisado . En el aprendizaje supervisado, se le dan a un algoritmo muestras que están etiquetadas de alguna manera útil. Por ejemplo, las muestras pueden ser descripciones de hongos y las etiquetas pueden indicar si los hongos son comestibles o no. El algoritmo toma estas muestras previamente etiquetadas y las usa 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 de 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. ^{[ cita requerida ]} En la teoría del aprendizaje computacional, un cálculo se considera factible si se puede realizar en tiempo polinomial . ^{[ cita requerida ]} Hay dos tipos de resultados de complejidad temporal:

• Resultados positivos: demuestra que una determinada clase de funciones se puede aprender en tiempo polinomial.
• Resultados negativos: muestran que ciertas clases no se pueden aprender en tiempo polinomial.

Los resultados negativos a menudo se basan en suposiciones comúnmente aceptadas, pero aún no probadas, ^{[ cita requerida ]} como:

• Complejidad computacional – P ≠ NP (el problema P versus NP) ;
• Criptográfico : Existen funciones unidireccionales .

Existen varios enfoques diferentes para la teoría del aprendizaje computacional que se basan en la realización de 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 suposiciones sobre la generación de muestras. ^{[ cita requerida ]} Los diferentes enfoques incluyen:

• Aprendizaje exacto, propuesto por Dana Angluin ^{[ cita requerida ]} ;
• Aprendizaje probablemente aproximadamente correcto (aprendizaje PAC), propuesto por Leslie Valiant ; ^[2]
• Teoría VC , propuesta por Vladimir Vapnik y Alexey Chervonenkis ; ^[3]
• Inferencia inductiva tal como la desarrolló Ray Solomonoff ; ^{[4] [5]}
• Teoría del aprendizaje algorítmico , del trabajo de E. Mark Gold ; ^[6]
• Aprendizaje automático en línea , del trabajo de Nick Littlestone ^{[ cita requerida ]} .

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 boosting , la teoría VC condujo a las máquinas de vectores de soporte y la inferencia bayesiana condujo a las redes de creencias .

Véase también

• Tolerancia a errores (aprendizaje PAC)
• Inducción gramatical
• Teoría de la información
• Aprendizaje de Occam
• Estabilidad (teoría del aprendizaje)

Referencias

1. "ACL - Asociación para el Aprendizaje Computacional".
2. Valiant, Leslie (1984). "Una teoría de lo aprendible" (PDF) . Comunicaciones de la ACM . 27 (11): 1134–1142. doi :10.1145/1968.1972. S2CID  12837541. Archivado desde el original (PDF) el 2019-05-17 . Consultado el 2022-11-24 .
3. Vapnik, V.; Chervonenkis, A. (1971). "Sobre la convergencia uniforme de frecuencias relativas de eventos con sus probabilidades" (PDF) . Teoría de la probabilidad y sus aplicaciones . 16 (2): 264–280. doi :10.1137/1116025.
4. Solomonoff, Ray (marzo de 1964). "Una teoría formal de la inferencia inductiva, parte 1". Información y control . 7 (1): 1–22. doi : 10.1016/S0019-9958(64)90223-2 .
5. Solomonoff, Ray (1964). "Una teoría formal de la inferencia inductiva, parte 2". Información y control . 7 (2): 224–254. doi :10.1016/S0019-9958(64)90131-7.
6. Gold, E. Mark (1967). "Identificación del lenguaje en el límite" (PDF) . Información y Control . 10 (5): 447–474. doi : 10.1016/S0019-9958(67)91165-5 .

Lectura adicional

En 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: estudio 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 correcto. En AAAI-90 Proceedings of the Eight National Conference on Artificial Intelligence, Boston, MA, páginas 1101–1108. Asociación Estadounidense de Inteligencia Artificial, 1990. http://citeseer.ist.psu.edu/haussler90probably.html

Selección de funciones

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

Aprendizaje óptimo de la notación O

• Oded Goldreich , Dana Ron . 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.º 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 ^{[ enlace roto ]}

Tolerancia de error

• 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 y 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 capacidad de aprendizaje polinomial, Proc. 1er Taller ACM sobre Teoría del Aprendizaje Computacional, (1988) 42-55.
• Pitt, L.; Warmuth, MK (1990). "Reducibilidad que preserva la predicción". Revista de Ciencias de la Computación y de Sistemas . 41 (3): 430–467. doi : 10.1016/0022-0000(90)90028-J .

Enlaces externos

• Fundamentos de la inferencia bayesiana