El aprendizaje de Occam

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 2 de julio de 2020; la verificación requiere 1 edición .

El aprendizaje de Ockham en la teoría del aprendizaje computacional es un modelo de aprendizaje algorítmico donde el objetivo del aprendizaje es obtener una representación concisa de los datos de entrenamiento disponibles. El método está estrechamente relacionado con el aprendizaje casi correcto (aprendizaje PC, ing. Aprendizaje probablemente aproximadamente correcto , aprendizaje PAC), donde el maestro evalúa la capacidad predictiva del conjunto de prueba.

La capacidad de aprendizaje de Occam implica el aprendizaje de PC, y para una amplia clase de conceptos, también es cierto lo contrario: el aprendizaje de PC implica el aprendizaje de Occam.

Introducción

El aprendizaje de Occam recibe su nombre del término " navaja de Occam ", que es el principio que establece que, suponiendo que no haya entidades adicionales, se debe preferir una breve explicación de las observaciones a una explicación más larga (brevemente: "Uno no debe multiplicar seres innecesariamente"). La teoría del aprendizaje de Occam es un refinamiento formal y matemático de este principio. Blumer y otros fueron los primeros en demostrar [1] que el aprendizaje de Occam implica el aprendizaje de PC, que es el modelo de aprendizaje estándar en la teoría del aprendizaje computacional. En otras palabras, la frugalidad (hipótesis de salida) implica capacidad predictiva .

Definición de aprendizaje de Occam

La concisión de un concepto en una clase de concepto se puede expresar como la longitud de la cadena de bits más corta que puede representar el concepto en la clase . El aprendizaje de Ockham conecta la concisión de la salida de un algoritmo de aprendizaje con su capacidad predictiva. $C$ ${\ matemáticas {C}}$ ${\ tamaño del estilo de visualización (c)}$ $C$ ${\ matemáticas {C}}$

Sean y sean clases de conceptos que contengan conceptos objetivo e hipótesis, respectivamente. Entonces, para constantes y , el algoritmo de aprendizaje es un algoritmo de -Occam para por hipótesis si y solo si, dado un conjunto que contiene instancias etiquetadas de acuerdo con , la salida del algoritmo es una hipótesis , tal que ${\ matemáticas {C}}$ ${\ matemáticas {H}}$ $\alpha \geqslant 0$ $0\leqslant\beta <1$ $L$ ${\ estilo de visualización (\ alfa, \ beta)}$ ${\ matemáticas {C}}$ ${\ matemáticas {H}}$ ${\displaystyle S=\{x\))$ $metro$ $c(x)\in {\mathcal {C))$ $L$ $h\in {\mathcal {H}}$

$h$ está de acuerdo con ( es decir, ) $C$ $S$ $h(x)=c(x),\forall x\in S$
${\displaystyle size(h)\leqslant (n\cdot size(c))^{\alpha }m^{\beta ))$ [2] [1]

donde es la longitud máxima de cualquier instancia de . El algoritmo de Occam se llama eficiente si se ejecuta en tiempo polinomial de y . Decimos que una clase de conceptos es aprendible por Occam con respecto a una clase de hipótesis si existe un algoritmo de Occam eficiente para por hipótesis $norte$ $x \ en S$ $norte$ $metro$ ${\ tamaño del estilo de visualización (c)}$ ${\ matemáticas {C}}$ ${\ matemáticas {H}}$ ${\ matemáticas {C}}$ ${\ matemáticas {H}).$

Relación entre el aprendizaje Occam y el aprendizaje PC

La capacidad de aprendizaje de Ockham implica la capacidad de aprendizaje de la PC, como muestra el teorema de Blumer et al [2] :

Teorema ( el aprendizaje de Occam implica el aprendizaje de PC )

Sea un algoritmo de -Occam eficiente para por hipótesis . Entonces hay una constante tal que para cualquiera para cualquier distribución , dadas instancias extraídas y etiquetadas de acuerdo con el concepto de cada bit, el algoritmo producirá una hipótesis tal que con probabilidad al menos $L$ ${\ estilo de visualización (\ alfa, \ beta)}$ ${\ matemáticas {C}}$ ${\ matemáticas {H}}$ $a>0$ $0<\epsilon,\delta <1$ ${\mathcal {D}}$ $m\geqslant a\left({\frac {1}{\epsilon }}\log {\frac {1}{\delta }}+\left({\frac {(n\cdot size(c) )^{\alpha })}{\epsilon }}\right)^{\frac {1}{1-\beta }}\right)$ $\mathcal{D}$ $c\in {\mathcal {C))$ $norte$ $L$ $h\in {\mathcal {H}}$ ${\ error de estilo de visualización (h) \ leqslant \ epsilon}$ ${\ estilo de visualización 1-\ delta}$

. Aquí se tiene en cuenta el concepto y la distribución . De ello se deduce que el algoritmo es un PC maestro de la clase de conceptos bajo la clase de hipótesis . Una formulación un poco más general: ${\ error de estilo de visualización (h)}$ $C$ ${\mathcal {D}}$ $L$ ${\ matemáticas {C}}$ ${\ matemáticas {H}}$

Teorema ( El aprendizaje de Occam implica el aprendizaje de PC, versión larga )

deja _ Sea un algoritmo tal que dado un conjunto de instancias extraídas de una distribución fija pero desconocida y etiquetadas de acuerdo con el concepto con una cadena de bits de longitud cada una, el resultado es una hipótesis consistente con las instancias etiquetadas. Entonces existe una constante tal que en caso de que se garantice dar una hipótesis tal que con probabilidad al menos . $0<\epsilon,\delta <1$ $L$ $metro$ $\mathcal{D}$ $c\in {\mathcal {C))$ $norte$ $h\in {\mathcal {H}}_{n,m}$ $b$ $\log |{\mathcal {H}}_{n,m}|\leqslant b\epsilon m-\log {\frac {1}{\delta }}$ $L$ $h\in {\mathcal {H}}_{n,m}$ ${\ error de estilo de visualización (h) \ leqslant \ epsilon}$ ${\ estilo de visualización 1-\ delta}$

Aunque los teoremas anteriores muestran que el aprendizaje de Occam es suficiente para el aprendizaje de PC, no dicen nada sobre la necesidad de . Board y Pitt han demostrado que para una amplia clase de conceptos, el aprendizaje de Occam es necesario para el aprendizaje de PC [3] . Demostraron que para cualquier clase de conceptos polinómicamente cerrados bajo las listas de excepción , la capacidad de aprendizaje de la PC implica la existencia de un algoritmo Occam para esa clase de conceptos. Las clases de conceptos que se cierran polinómicamente mediante listas de excepciones incluyen fórmulas booleanas, cadenas de suma, autómatas finitos deterministas , listas de decisiones, árboles de decisiones y otras clases de conceptos con base geométrica.

Una clase de conceptos se cierra polinómicamente en listas de excepciones si existe un algoritmo de tiempo de ejecución polinomial , tal que, dada una representación del concepto y una lista finita de excepciones , la salida del algoritmo es una representación del concepto , tal que los conceptos y aceptan salvo la exclusión de elementos del conjunto . ${\ matemáticas {C}}$ $A$ $c\in {\mathcal {C))$ $mi$ $c'\in {\mathcal {C}}$ $C$ $C'$ $mi$

Prueba de que el aprendizaje de Occam implica el aprendizaje de PC

Primero probaremos la versión con longitud. Llamamos mala a la hipótesis si , donde nuevamente se tiene en cuenta el verdadero concepto y distribución de . La probabilidad de que el conjunto sea consistente con no excede de , según la independencia de las muestras. Para un conjunto completo, la probabilidad de que haya una mala hipótesis en no excede , que es menor que si . Esto completa la demostración del segundo teorema. $h\in {\mathcal {H}}$ ${\ error de estilo de visualización (h) \ geqslant \ epsilon}$ ${\ error de estilo de visualización (h)}$ $C$ $\mathcal{D}$ $S$ $h$ ${\displaystyle (1-\epsilon)^{m))$ ${\mathcal {H}}_{n,m}$ $|{\mathcal {H}}_{n,m}|(1-\epsilon)^{m}$ ${\ estilo de visualización \ delta}$ $\log |{\mathcal {H}}_{n,m}|\leqslant O(\epsilon m)-\log {\frac {1}{\delta }}$

Usando el segundo teorema, probaremos el primero. Dado que tenemos un algoritmo -Occam, esto significa que cualquier hipótesis de salida del algoritmo se puede representar como máximo con bits, y luego . Esto es menor que si establecemos alguna constante . Entonces, según la versión del teorema con longitud, dará una hipótesis consistente con una probabilidad de al menos . Esto completa la demostración del primer teorema. ${\ estilo de visualización (\ alfa, \ beta)}$ $L$ $(n\cdot size(c))^{\alpha }m^{\beta }$ $\log |{\mathcal {H}}_{n,m}|\leqslant (n\cdot size(c))^{\alpha }m^{\beta }$ $O(\epsilon m)-\log {\frac {1}{\delta }}$ $m\geqslant a\left({\frac {1}{\epsilon }}\log {\frac {1}{\delta }}+\left({\frac {(n\cdot size(c) )^{\alpha })}{\epsilon }}\right)^{\frac {1}{1-\beta }}\right)$ $a>0$ $L$ $h$ ${\ estilo de visualización 1-\ delta}$

Mejora de la complejidad de la muestra para problemas generales

Aunque el aprendizaje de Occam y el aprendizaje de PC son equivalentes, el algoritmo de Occam se puede usar para obtener límites más estrictos en la complejidad de la muestra para problemas clásicos, incluido el razonamiento lógico [2] , el razonamiento multivariable [4] y las listas de decisiones [5] .

Extensiones

Se ha demostrado que los algoritmos de Ockham funcionan con éxito para el aprendizaje de PT en presencia de errores [6] [7] , el aprendizaje de conceptos probabilísticos [8] , el aprendizaje de funciones [9] y los ejemplos de Markov no independientes [10] .

Véase también

Minimización del riesgo estructural
Teoría del aprendizaje computacional

Notas

↑ 1 2 Blumer, Ehrenfeucht, Haussler, Warmuth, 1987 , p. 377-380.
↑ 1 2 3 Kearns, Vazirani, 1994 .
↑ Junta, Pitt, 1990 , p. 54-63.
↑ Haussler, 1988 , pág. 177-221.
↑ Rivest, 1987 , pág. 229-246.
↑ Angluin, Laird, 1988 , p. 343-370.
↑ Kearns, Li, 1993 , pág. 807-837.
↑ Kearns, Schapire, 1990 , pág. 382-391.
↑ Natarajan, 1993 , pág. 370-376.
↑ Aldous y Vazirani 1990 , p. 392-396.

Literatura

Kearns MJ, Vazirani UV capítulo 2 // Una introducción a la teoría del aprendizaje computacional. - Prensa del MIT, 1994. - ISBN 9780262111935 .
Blumer A., Ehrenfeucht A., Haussler D., Warmuth M. K. La navaja de Occam . - 1987. - T. 24 , núm. 6 _ - doi : 10.1016/0020-0190(87)90114-1 .
Board R., Pitt L. Sobre la necesidad de los algoritmos de Occam // Actas del vigésimo segundo simposio anual de ACM sobre Teoría de la computación. — ACM, 1990.
Haussler D. Cuantificación del sesgo inductivo: algoritmos de aprendizaje de IA y marco de aprendizaje de Valiant // Inteligencia artificial. - 1988. - T. 36 , núm. 2 . Archivado desde el original el 12 de abril de 2013.
Rivest RL Listas de decisiones de aprendizaje // Aprendizaje automático. - 1987. - Vol. 2 , número. 3 .
Angluin D., Laird P. Aprendiendo de ejemplos ruidosos // Aprendizaje automático. - 1988. - Vol. 2 , número. 4 .
Kearns M., Li M. Aprendizaje en presencia de errores maliciosos // SIAM Journal on Computing,. - 1993. - T. 22 , núm. 4 .

Kearns MJ, Schapire RE Aprendizaje eficiente sin distribución de conceptos probabilísticos // Fundamentos de Ciencias de la Computación, 1990. Actas., 31° Simposio Anual . - Los Alamitos, CA: IEEE Computer Society Press, 1990.

- Kearns MJ, Schapire RE Fundamentos de Ciencias de la Computación, 1990. Actas., 31° Simposio Anual // REVISTA DE CIENCIAS DE COMPUTACIÓN Y SISTEMAS. - 1994. - Edición. 48 . - S. 464-497 .
La navaja para funciones de Natarajan BK Occam // Actas de la sexta conferencia anual sobre teoría del aprendizaje computacional. — ACM, 1993.

Aldous D., Vazirani U. Una extensión markoviana del modelo de aprendizaje de Valiant // Fundamentos de la informática, 1990. Actas., 31.º Simposio anual. —IEEE, 1990.

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