Teoría del aprendizaje computacional

Ver también: teoría del aprendizaje estadístico

Teoría del aprendizaje automático

Este artículo necesita citas adicionales para su verificación . Por favor, ayuda a mejorar este artículo mediante la adición de citas de fuentes confiables . El material no obtenido puede ser cuestionado y eliminado. Encuentre fuentes:  "Teoría del aprendizaje computacional"  -  noticias  · periódicos  · libros  · académico  · JSTOR ( noviembre de 2018 ) ( Aprenda cómo y cuándo eliminar este mensaje de plantilla )

Parte de una serie sobre
Aprendizaje automático y minería de datos
Problemas Clasificación Agrupación Regresión Detección de anomalías AutoML reglas de asociación Aprendizaje reforzado Predicción estructurada Ingeniería de características Aprendizaje de funciones Aprender en línea Aprendizaje semi-supervisado Aprendizaje sin supervisión Aprendiendo a clasificar Inducción gramatical
Aprendizaje supervisado ( clasificación  • regresión ) Árboles de decisión Conjuntos Harpillera Impulsando Bosque aleatorio k -NN Regresión lineal Bayes ingenuo Redes neuronales artificiales Regresión logística Perceptrón Máquina de vectores de relevancia (RVM) Máquina de vectores de soporte (SVM)
Agrupación ABEDUL CURA Jerárquico k -significa Expectativa-maximización (EM) DBSCAN ÓPTICA Cambio medio
Reducción de dimensionalidad Análisis factorial CCA ICA LDA NMF PCA PGD t-SNE
Predicción estructurada Modelos graficos Red de Bayes Campo aleatorio condicional Markov oculto
Detección de anomalías k -NN Factor de valor atípico local
Red neuronal artificial Autoencoder Computación cognitiva Aprendizaje profundo DeepDream Perceptrón multicapa RNN LSTM GRU ESN Máquina de Boltzmann restringida GAN SOM Red neuronal convolucional U-Net Transformador Red neuronal en aumento Memtransistor RAM electroquímica (ECRAM)
Aprendizaje reforzado Q-aprendizaje SARSA Diferencia temporal (TD)
Teoría Compensación entre sesgo y varianza Teoría del aprendizaje computacional Minimización de riesgos empíricos Aprendizaje de Occam Aprendizaje PAC Aprendizaje estadístico Teoría de VC
Lugares de aprendizaje automático NeurIPS ICML ML JMLR ArXiv: cs.LG
Artículos relacionados Glosario de inteligencia artificial Lista de conjuntos de datos para la investigación de aprendizaje automático Esquema del aprendizaje automático
v t mi

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 . ^[1]

Resumen

Los resultados teóricos en el aprendizaje automático se refieren principalmente a un tipo de aprendizaje inductivo llamado aprendizaje supervisado . En el aprendizaje supervisado, un algoritmo recibe 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 anteriormente. El objetivo del algoritmo de aprendizaje supervisado es optimizar alguna medida de rendimiento, como minimizar el número de errores cometidos en nuevas muestras.

Además de los límites de rendimiento, la teoría del aprendizaje computacional estudia la complejidad del tiempo y la viabilidad del aprendizaje. ^{[ cita requerida ]} En la teoría del aprendizaje computacional, un cálculo se considera factible si se puede hacer en tiempo polinomial . ^{[ cita requerida ]} Hay dos tipos de resultados de complejidad temporal:

• Resultados positivos: muestra 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 creídas, pero aún no probadas, ^{[ cita requerida ]} como:

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

Hay varios enfoques diferentes de la teoría del aprendizaje computacional que se basan 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. ^{[ cita requerida ]} Los diferentes enfoques incluyen: ^{[ cita requerida ]}

• Aprendizaje exacto, propuesto por Dana Angluin ;
• Probablemente aprendizaje aproximadamente correcto ( aprendizaje PAC), propuesto por Leslie Valiant ;
• Teoría de VC , propuesta por Vladimir Vapnik y Alexey Chervonenkis ;
• Inferencia bayesiana ;
• 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 máquinas de vectores de soporte y la inferencia bayesiana condujo a redes de creencias .

Ver también

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

Referencias

1. "ACL - Asociación para el aprendizaje computacional" .

Encuestas

• Angluin, D. 1992. Teoría del aprendizaje computacional: Encuesta y bibliografía seleccionada. En Actas del Vigésimo Cuarto Simposio Anual de 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. Probablemente un aprendizaje aproximadamente 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

Dimensión VC

• V. Vapnik y A. Chervonenkis. Sobre la convergencia uniforme de frecuencias relativas de eventos a sus probabilidades . Teoría de la probabilidad y sus aplicaciones, 16 (2): 264-280, 1971.

Selección de funciones

• A. Dhagat y L. Hellerstein, "Aprendizaje de PAC con atributos irrelevantes", en 'Proceedings of the IEEE Symp. on Foundation of Computer Science ', 1994. http://citeseer.ist.psu.edu/dhagat94pac.html

Inferencia inductiva

• Gold, E. Mark (1967). "Identificación de idiomas en el límite" (PDF) . Información y control . 10 (5): 447–474. doi : 10.1016 / S0019-9958 (67) 91165-5 .

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 sobre el aprendizaje de fórmulas booleanas y autómatas finitos. En Proceedings of the 21st Annual ACM Symposium on Theory of Computing, páginas 433–444, Nueva York. ACM. http://citeseer.ist.psu.edu/kearns89cryptographic.html

Impulso (aprendizaje automático)

• Robert E. Schapire. La fuerza de pobre aprendizaje. Aprendizaje automático, 5 (2): 197–227, 1990 http://citeseer.ist.psu.edu/schapire90strength.html

Occam Learning

• Blumer, A .; Ehrenfeucht, A .; Haussler, D .; Warmuth, la navaja de MK Occam Inf.Proc.Lett. 24, 377–380, 1987.
• Blumer, A .; Ehrenfeucht, A .; Haussler, D .; Warmuth, MK Learnability y la dimensión Vapnik-Chervonenkis . Journal of the ACM, 36 (4): 929–865, 1989.

Probablemente aprendizaje aproximadamente correcto

• L. Valiant. Una teoría de lo aprendible . Comunicaciones de la ACM, 27 (11): 1134-1142, 1984.

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 y tolerante al ruido a partir de consultas estadísticas. En Actas del Vigésimo Quinto Simposio Anual de 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 de preservación de predicción". Revista de Ciencias de la Computación y Sistemas . 41 (3): 430–467. doi : 10.1016 / 0022-0000 (90) 90028-J .

Se ofrece una descripción de algunas de estas publicaciones en publicaciones importantes sobre aprendizaje automático .

Teoría del aprendizaje de la distribución

Enlaces externos

• Conceptos básicos de la inferencia bayesiana