Teoría del aprendizaje computacional

La teoría del aprendizaje computacional ( en inglés Computational Learning Theory , o simplemente teoría del aprendizaje ) es un subcampo de la teoría de la inteligencia artificial , dedicado al desarrollo y análisis de algoritmos de aprendizaje automático [1] .

Resumen

Los resultados teóricos en el aprendizaje automático se ocupan principalmente del aprendizaje inductivo, que se denomina aprendizaje supervisado . Con este enfoque, el algoritmo recibe muestras etiquetadas de alguna manera. Por ejemplo, las muestras pueden ser descripciones de hongos y la etiqueta determina si el hongo es comestible o no. El algoritmo toma estas muestras etiquetadas y las usa para obtener el clasificador . El clasificador es una función que asigna etiquetas a las muestras, incluidas las muestras que el algoritmo no ha escaneado previamente. El objetivo del aprendizaje supervisado es optimizar alguna medida de rendimiento, como minimizar la cantidad de errores cometidos en nuevas muestras.

Además de la frontera de eficiencia, la teoría del aprendizaje computacional estudia la complejidad temporal y la realizabilidad de un algoritmo. En la teoría del aprendizaje computacional, se dice que un cálculo es realizable si se puede realizar en tiempo polinomial . Hay dos tipos de complejidad temporal de los resultados:

Los resultados positivos muestran que algunas clases de funciones pueden ser entrenadas en tiempo polinomial.
Los resultados negativos muestran que alguna clase de funciones no se pueden aprender en tiempo polinomial.

Los resultados negativos a menudo se basan en ciertas afirmaciones que se creen pero no se prueban, como:

Complejidad computacional - P ≠ NP ;
Criptografía : existen funciones unidireccionales .

Hay varios enfoques diferentes para la teoría del aprendizaje computacional. Estas diferencias se basan en suposiciones sobre los principios de inferencia utilizados para generalizar a partir de datos limitados. Estos principios incluyen la definición de probabilidad (ver probabilidad de frecuencia , probabilidad bayesiana ) y varios supuestos sobre la generación de muestras. Varios enfoques incluyen:

Aprendizaje preciso sugerido por Dana Angluin ;
Aprendizaje Probabilísticamente Aproximadamente Correcto (PCL) propuesto por Leslie Valiant ;
la teoría de Vapnik-Chervonenkis propuesta por Vladimir Vapnik y Alexei Chervonenkis ;
inferencia bayesiana ;
Teoría del aprendizaje algorítmico de E. Mark Gold;
Aprendizaje automático en línea del trabajo de Nick Littlestone.

La teoría del aprendizaje computacional conduce a algunos algoritmos prácticos. Por ejemplo, la teoría VPK dio origen al impulso , la teoría de Vapnik-Chervonenkis condujo a las máquinas de vectores de soporte y la inferencia bayesiana condujo a las redes bayesianas (autor: Judah Pearl ).

Véase también

Derivación gramatical
Teoría de la información
Estabilidad (teoría del aprendizaje)
Tolerancia a fallas (entrenamiento VPK)
Dimensión Vapnik-Chervonenkis
selección de características
razonamiento inductivo
O-learning óptimo
impulsar
El aprendizaje de Occam
Probablemente entrenamiento aproximadamente correcto
Teoría del aprendizaje distribuido

Notas

↑ ACL: Asociación para el aprendizaje computacional . Consultado el 5 de diciembre de 2018. Archivado desde el original el 25 de enero de 2012. (indefinido)

Literatura

Angluin D. Teoría del aprendizaje computacional: encuesta y bibliografía seleccionada // Actas del vigésimo cuarto simposio anual de ACM sobre teoría de la computación (mayo de 1992. - 1992. - P. 351-369.
Haussler D. Probablemente un aprendizaje aproximadamente correcto // AAAI-90 Actas de la Octava Conferencia Nacional sobre Inteligencia Artificial, Boston, MA . - Asociación Americana de Inteligencia Artificial, 1990. - S. 1101-1108.
Vapnik V., Chervonenkis A. Sobre la convergencia uniforme de frecuencias relativas de eventos a sus probabilidades // Teoría de la probabilidad y sus aplicaciones. - 1971. - T. 16 , núm. 2 . — S. 264–280 .
Dhagat A., Hellerstein L. Aprendizaje de PAC con atributos irrelevantes // Actas del IEEE Symp. sobre Fundamentos de Informática . — 1994.
E. Marcos de oro. Identificación de idiomas en el límite // Información y Control. - 1967. - T. 10 , núm. 5 . — S. 447–474 . - doi : 10.1016/S0019-9958(67)91165-5 .
Oded Goldreich, Dana Ron. Sobre algoritmos universales de aprendizaje . resumen
Kearns M., Leslie Valiant. Limitaciones criptográficas en el aprendizaje de fórmulas booleanas y autómatas finitos // Actas del 21.º Simposio Anual de ACM sobre Teoría de la Computación . - Nueva York: ACM, 1989. - S. 433-444.
Robert E. Schapire. La fuerza del aprendizaje débil // Machine Learning. - 1990. - V. 5 , núm. 2 . — S. 197–227 .
Blumer A., Ehrenfeucht A., Haussler D., Warmuth MK La navaja de Occam // Inf.Proc.Lett.. - 1987. - V. 24 . — S. 377–380 .
Blumer A., Ehrenfeucht A., Haussler D., Warmuth MK Learnability and the Vapnik-Chervonenkis dimension // Journal of the ACM. - 1989. - T. 36 , núm. 4 . — S. 929–865 .
Valiant L. A Theory of the Learnable // Communications of the ACM. - 1984. - T. 27 , núm. 11 _ — S. 1134–1142 .
Michael Kearns, Ming Li. Aprendizaje en presencia de errores maliciosos // SIAM Journal on Computing. - 1993. - Agosto ( vol. 22 , número 4 ). — S. 807–837 .
Michael Kearns. Aprendizaje tolerante al ruido eficiente a partir de consultas estadísticas // Actas del vigésimo quinto simposio anual de ACM sobre teoría de la computación . - 1993. - S. 392-401.
Haussler D., Kearns M., Littlestone N., Warmuth M. Equivalencia de modelos para la capacidad de aprendizaje de polinomios // Proc. 1er Taller ACM sobre Teoría del Aprendizaje Computacional. - 1988. - S. 42-55.
Pitt L., Warmuth MK Predicción-Preservación de la reducibilidad // Journal of Computer and System Sciences. - 1990. - T. 41 , núm. 3 . — S. 430–467 . - doi : 10.1016/0022-0000(90)90028-J .

Enlaces

Conceptos básicos de la inferencia bayesiana

Aprendizaje automático y minería de datos
Tareas	Problema de clasificación Aprender sin un maestro Aprendizaje asistido por profesores Análisis de regresión AutoML reglas de asociación Extracción de características entrenamiento de rasgos Entrenamiento de clasificación Derivación gramatical Aprender en línea
Aprendiendo con un maestro	método del k-vecino más cercano Clasificador bayesiano ingenuo árbol de decisión Máquinas de vectores soporte Regresión lineal Regresión logística perceptrón conjuntos de modelos Harpillera impulsar bosque aleatorio Método de vector relevante
análisis de conglomerados	método k-medias método de agrupamiento difuso Agrupación jerárquica algoritmo EM ABEDUL CURAR DBSCAN ÓPTICA Desplazamiento medio
Reducción de dimensionalidad	Análisis factorial Método de componentes principales CCA ICA LDA Expansión de matriz no negativa t-SNE
Pronóstico estructural	Graficar modelo probabilístico red bayesiana Modelo oculto de Markov FRC
Detección de anomalías	método del k-vecino más cercano Nivel de emisión local
Graficar modelos probabilísticos	red bayesiana Red de Markov Modelo oculto de Markov
Redes neuronales	Máquina Boltzmann limitada mapa autoorganizado Función de activación Sigmoideo softmax Funcion de base radial Método de propagación hacia atrás Aprendizaje profundo perceptrón multicapa Red neuronal recurrente memoria a corto plazo Bloque recurrente controlado Red neuronal convolucional U-red Codificador automático
Aprendizaje reforzado	proceso de Markov Ecuación de Bellman Algoritmo codicioso Q-aprendizaje SARAS Diferencia temporal (DT)
Teoría	Teoría de Vapnik-Chervonenkis Dilema de dispersión de sesgo Teoría del aprendizaje computacional Minimización empírica del riesgo El aprendizaje de Occam aprendizaje PAC Teoría del aprendizaje estadístico
revistas y congresos	NeurIPS ICML ML JMLR ArXiv:cs.LG