Teoría del aprendizaje computacional - Computational learning theory

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 .

Descripción general

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. En la teoría del aprendizaje computacional, un cálculo se considera factible si se puede realizar en tiempo polinomial . Hay dos tipos de resultados de complejidad temporal:

• Resultados positivos: muestran 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, 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. Los diferentes enfoques incluyen:

• 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

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 características

• 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

Aprendizaje Occam

• 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. Valiente. 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