¿Cuáles son los principales teoremas del aprendizaje automático (profundo)?

Al Rahimi recientemente dio una charla muy provocativa en NIPS 2017 comparando el aprendizaje automático actual con la alquimia. Una de sus afirmaciones es que necesitamos volver a los desarrollos teóricos, tener teoremas simples que demuestren resultados fundamentales.

Cuando dijo eso, comencé a buscar los teoremas principales para ML, pero no pude encontrar una buena referencia que tuviera sentido de los resultados principales. Así que aquí está mi pregunta: ¿cuáles son los principales teoremas matemáticos actuales (teoría) en ML / DL y qué prueban? Supongo que el trabajo de Vapnik iría a algún lado aquí. Como extra, ¿cuáles son los principales problemas teóricos abiertos?

Como escribí en los comentarios, esta pregunta me parece demasiado amplia, pero intentaré responder. Con el fin de establecer algunos límites, comenzaré con un poco de matemática que subyace a la mayoría de ML y luego me concentraré en los resultados recientes para DL.

---

El equilibrio de sesgo-varianza se menciona en innumerables libros, cursos, MOOC, blogs, tweets, etc. en ML, por lo que no podemos comenzar sin mencionarlo:

$$\mathbb{E}[(Y-\hat{f}(X))^2|X=x_0]=\sigma_{\epsilon}^2+\left(\mathbb{E}\hat{f}(x_0)-f(x_0)\right)^2+\mathbb{E}\left[\left(\hat{f}(x_0)-\mathbb{E}\hat{f}(x_0)\right)^2\right]=\text{Irreducible error + Bias}^2 \text{ + Variance}$$

Prueba aquí: https://web.stanford.edu/~hastie/ElemStatLearn/

---

El teorema de Gauss-Markov (sí, la regresión lineal seguirá siendo una parte importante del aprendizaje automático, no importa qué: lidiar con él) aclara que, cuando el modelo lineal es verdadero y algunos supuestos sobre el término de error son válidos, OLS tiene el mínimo error cuadrático medio (que en la expresión anterior es sólo ) sólo entre los imparciales estimadores lineales del modelo lineal. Por lo tanto, bien podría haber estimadores lineales con sesgo (o estimadores no lineales) que tengan un mejor error cuadrático medio y, por lo tanto, un mejor error de predicción esperado, que los MCO. Y esto allana el camino a todo el arsenal de regularización (regresión de crestas, LASSO, pérdida de peso, etc.) que es un caballo de batalla de ML. Aquí se proporciona una prueba (y en muchos otros libros): $\text{Bias}^2 \text{ + Variance}$https://www.amazon.com/Linear-Statistical-Models-James-Stapleton/dp/0470231467

Probablemente más relevante para la explosión de los enfoques de regularización, como señaló Carlos Cinelli en los comentarios, y definitivamente más divertido de aprender, es el teorema de James-Stein . Considere independientes, la misma varianza pero no las mismas variables aleatorias gaussianas medias:$n$

$$X_i|\mu_i\sim \mathcal{N}(\theta_i,\sigma^2), \quad i=1,\dots,n$$

en otras palabras, tenemos un vector aleatorio gaussiano de componentes . Tenemos una muestra de y queremos estimar . El estimador MLE (y también UMVUE) es obviamente . Considere el estimador James-Stein$n-$$\mathbf{X}\sim \mathcal{N}(\boldsymbol{\theta},\sigma^2I)$$\mathbf{x}$$\mathbf{X}$$\boldsymbol{\theta}$$\hat{\boldsymbol{\theta}}_{MLE}=\mathbf{x}$

$$\hat{\boldsymbol{\theta}}_{JS}= \left(1-\frac{(n-2)\sigma^2}{||\mathbf{x}||^2}\right)\mathbf{x}$$

Claramente, si , reduce la estimación de MLE hacia cero. El teorema de James-Stein establece que para , domina estrictamente , es decir, tiene un MSE más bajo . Sorprendentemente, incluso si nos encogemos hacia cualquier otra constante , todavía domina . Desde el$(n-2)\sigma^2\leq||\mathbf{x}||^2$$\hat{\boldsymbol{\theta}}_{JS}$ $n\geq4$$\hat{\boldsymbol{\theta}}_{JS}$ $\hat{\boldsymbol{\theta}}_{MLE}$$\forall \ \boldsymbol{\theta}$$\boldsymbol{c}\neq \mathbf{0}$$\hat{\boldsymbol{\theta}}_{JS}$$\hat{\boldsymbol{\theta}}_{MLE}$$X_i$son independientes, puede parecer extraño que, al tratar de estimar la altura de tres personas no relacionadas, incluida una muestra del número de manzanas producidas en España, pueda mejorar nuestra estimación en promedio . El punto clave aquí es "en promedio": el error cuadrado medio para la estimación simultánea de todos los componentes del vector de parámetros es menor, pero el error cuadrado para uno o más componentes bien puede ser mayor, y de hecho a menudo lo es, cuando tienes observaciones "extremas".

Descubrir que MLE, que de hecho era el estimador "óptimo" para el caso de estimación univariante, fue destronado para la estimación multivariada, fue un shock en ese momento y generó un gran interés en la contracción, mejor conocida como regularización en lenguaje ML. Uno podría notar algunas similitudes con los modelos mixtos y el concepto de "fuerza de endeudamiento": de hecho, hay alguna conexión, como se discute aquí

Visión unificada sobre la contracción: ¿cuál es la relación (si la hay) entre la paradoja de Stein, la regresión de cresta y los efectos aleatorios en modelos mixtos?

Referencia: James, W., Stein, C., Estimación con pérdida cuadrática . Actas del Cuarto Simposio de Berkeley sobre Estadística matemática y probabilidad, Volumen 1: Contribuciones a la teoría de la estadística, 361-379, University of California Press, Berkeley, California, 1961

---

El análisis de componentes principales es clave para el tema importante de la reducción de dimensiones, y se basa en la descomposición del valor singular : para cada matriz real (aunque el teorema se generaliza fácilmente a matrices complejas) podemos escribir$N\times p$$X$

$$X=UDV^T$$

donde de tamaño es ortogonal, es una matriz diagonal con elementos diagonales no negativos y de tamaño es nuevamente ortogonal. Para ver pruebas y algoritmos sobre cómo calcularlo, ver: Golub, G. y Van Loan, C. (1983), Matrix computations , John Hopkins University press, Baltimore.$U$$N \times p$$D$$p \times p$$U$$p \times p$

---

El teorema de Mercer es la piedra angular de muchos métodos de ML diferentes: estrías de placas delgadas, máquinas de vectores de soporte, la estimación de Kriging de un proceso aleatorio gaussiano, etc. Básicamente, es uno de los dos teoremas detrás del llamado truco del núcleo . Deje que sea ​​una función continua simétrica o núcleo. si es positivo semidefinido, entonces admite una base ortornormal de funciones propias correspondientes a valores propios no negativos:$K(x,y):[a,b]\times[a,b]\to\mathbb{R}$$K$

$$K(x,y)=\sum_{i=1}^\infty\gamma_i \phi_i(x)\phi_i(y)$$

La importancia de este teorema para la teoría de ML está atestiguada por la cantidad de referencias que obtiene en textos famosos, como por ejemplo el texto de Rasmussen & Williams sobre procesos gaussianos .

Referencia: J. Mercer, Funciones de tipo positivo y negativo, y su conexión con la teoría de ecuaciones integrales. Transacciones filosóficas de la Royal Society de Londres. Serie A, que contiene documentos de carácter matemático o físico, 209: 415-446, 1909

También hay una presentación más simple en Konrad Jörgens, Operadores integrales lineales , Pitman, Boston, 1982.

---

El otro teorema que, junto con el teorema de Mercer, establece la base teórica del truco del núcleo, es el teorema del representador . Supongamos que tiene un espacio muestral y un núcleo semidefinido simétrico positivo . También dejó ser los RKHS asociados con . Finalmente, deje que sea ​​una muestra de entrenamiento. El teorema dice que entre todas las funciones , que admiten una representación infinita en términos de funciones propias de$\mathcal{X}$$K: \mathcal{X} \times \mathcal{X}\to \mathbb{R}$$\mathcal{H}_K$$K$$S=\{\mathbb{x}_i,y_i\}_{i=1}^n$$f\in \mathcal{H}_K$$K$Debido al teorema de Mercer, el que minimiza el riesgo regularizado siempre tiene una representación finita en la base formada por el núcleo evaluado en los puntos de entrenamiento, es decir$n$

$$\min_{f \in \mathcal{H}_K} \sum_{i=1}^n L(y_i,f(x_i))+\lambda||f||^2_{\mathcal{H}_K}=\min_{\{c_j\}_1^\infty} \sum_{i=1}^n L(y_i,\sum_j^\infty c_j\phi_j(x_i))+\lambda\sum_j^\infty \frac{c_j^2}{\gamma_j}=\sum_{i=1}^n\alpha_i K(x,x_i)$$

(El teorema es la última igualdad). Referencias: Wahba, G. 1990, Spline Models for Observational Data , SIAM, Philadelphia.

---

El teorema de aproximación universal ya ha sido citado por el usuario Tobias Windisch y es mucho menos relevante para el aprendizaje automático que para el análisis funcional, incluso si no lo parece a primera vista. El problema es que el teorema solo dice que dicha red existe, pero:

• no proporciona ninguna correlación entre el tamaño de la capa oculta y alguna medida de complejidad de la función objetivo , como por ejemplo, Variación total. Si y la requerida para un error fijo creció exponencialmente con , entonces una sola capa neural oculta Las redes serían inútiles.$N$$f(x)$$f(x)=\sin(\omega x):[0,2\pi]\to[-1,1]$$N$$\epsilon$$\omega$
• no dice si la red se puede aprender . En otras palabras, suponga que dados y , sabemos que un tamaño NN se aproximará a con la tolerancia requerida en el hipercubo. Luego, mediante el uso de conjuntos de entrenamiento de tamaño y un procedimiento de aprendizaje como, por ejemplo, respaldo, ¿tenemos alguna garantía de que al aumentar podamos recuperar ?$F(x)$$f$$\epsilon$$N$$f$$M$$M$$F$
• finalmente, y lo peor de todo, no dice nada sobre el error de predicción de las redes neuronales. Lo que realmente estamos interesados es una estimación del error de predicción, al menos como media de todas las series de entrenamiento de tamaño . El teorema no ayuda a este respecto.$M$

Un punto de dolor menor con la versión de Hornik de este teorema es que no es válido para las funciones de activación de ReLU. Sin embargo, Bartlett ha demostrado desde entonces una versión extendida que cubre esta brecha.

---

Hasta ahora, supongo que todos los teoremas que consideraba eran conocidos por cualquiera. Así que ahora es el momento de lo divertido :-) Veamos algunos teoremas de Deep Learning :

Suposiciones

• la red neuronal profunda (para fijo , es la función que asocia las entradas de la red neuronal con sus salidas) y la pérdida de regularización son sumas positivas funciones homogéneas del mismo grado$\Phi(X,W)$$W$$\Phi_W(X)$$\Theta(W)$
• la función de pérdida es convexa y una vez diferenciable en , en un conjunto compacto$L(Y,\Phi(X,W)$$X$$S$

Entonces:

• cualquier mínimo local para modo que una subred de tenga cero pesos, es un mínimo global ( Teorema 1 )$L(Y,\Phi(X,W))+\lambda\Theta(W)$$\Phi(X,W)$
• por encima de un tamaño de red crítico, el descenso local siempre convergerá a un mínimo global desde cualquier inicialización ( Teorema 2 ).

Esto es muy interesante: los CNN hechos solo de capas convolucionales, ReLU, agrupación máxima, ReLU completamente conectada y capas lineales son funciones positivamente homogéneas , mientras que si incluimos funciones de activación sigmoidea, esto ya no es cierto, lo que puede explicar en parte el superior rendimiento en algunas aplicaciones de ReLU + max pooling con respecto a los sigmoides. Además, los teoremas solo se mantienen si también es positivamente homogéneo en del mismo grado que . Ahora, el hecho divertido es que la regularización o , aunque positivamente homogénea, no tiene el mismo grado de (el grado de$\Theta$$W$$\Phi$$l_1$$l_2$$\Phi$$\Phi$, en el caso simple de CNN mencionado anteriormente, aumenta con el número de capas). En cambio, los métodos de regularización más modernos, como la normalización por lotes y la ruta SGD, corresponden a una función de regularización positivamente homogénea del mismo grado que , y el abandono, aunque no se ajusta exactamente a este marco, tiene fuertes similitudes con él. Esto puede explicar por qué, para obtener una alta precisión con las regularización y no es suficiente, ¡pero necesitamos emplear todo tipo de trucos diabólicos, como la deserción y la normalización de lotes! Que yo sepa, esto es lo más parecido a una explicación de la eficacia de la normalización de lotes, que por lo demás es muy oscura, como lo señaló correctamente Al Rahimi en su charla.$\Phi$$l_1$$l_2$

Otra observación que algunas personas hacen, basada en el Teorema 1 , es que podría explicar por qué ReLU funciona bien, incluso con el problema de las neuronas muertas . Según esta intuición, el hecho de que, durante el entrenamiento, algunas neuronas ReLU "mueren" (pasan a activación cero y luego nunca se recuperan de eso, ya que para el gradiente de ReLU es cero) es "una característica, no un error ", porque si hemos alcanzado un mínimo y una subred completa ha muerto, es probable que alcancemos un mínimo global (según las hipótesis del Teorema 1$x<0$) Puede que me falte algo, pero creo que esta interpretación es descabellada. En primer lugar, durante el entrenamiento, las ReLU pueden "morir" mucho antes de que alcancemos un mínimo local. En segundo lugar, debe demostrarse que cuando las unidades ReLU "mueren", siempre lo hacen en una subred completa: el único caso en el que esto es trivialmente cierto es cuando solo tiene una capa oculta, en cuyo caso, por supuesto, cada neurona es Una subred. Pero, en general, sería muy cauteloso al ver que las "neuronas muertas" son algo bueno.

Referencias

B. Haeffele y R. Vidal, Optimización global en la formación de redes neuronales , en la Conferencia IEEE sobre visión por computadora y reconocimiento de patrones, 2017.

B. Haeffele y R. Vidal. Optimización global en factorización de tensor, aprendizaje profundo y más allá , arXiv, abs / 1506.07540, 2015.

---

La clasificación de imágenes requiere representaciones de aprendizaje que son invariables (o al menos robustas, es decir, muy débilmente sensibles) a diversas transformaciones como ubicación, pose, punto de vista, iluminación, expresión, etc., que comúnmente están presentes en imágenes naturales, pero que no contienen información para la tarea de clasificación. Lo mismo para el reconocimiento de voz: cambios de tono, volumen, ritmo, acento. etc. no debe conducir a un cambio en la clasificación de la palabra. Las operaciones como convolución, agrupación máxima, agrupación promedio, etc., utilizadas en CNN tienen exactamente este objetivo, por lo que intuitivamente esperamos que funcionen para estas aplicaciones. ¿Pero tenemos teoremas para apoyar esta intuición? Hay un teorema de invariancia de traducción vertical, que, a pesar del nombre, no tiene nada que ver con la traducción en la dirección vertical, pero es básicamente un resultado que dice que las características aprendidas en las siguientes capas se vuelven cada vez más invariables, a medida que aumenta el número de capas. Esto se opone a un teorema de invariancia de traducción horizontal más antiguo que, sin embargo, es válido para las redes de dispersión, pero no para las CNN. El teorema es muy técnico, sin embargo:

• suponga que (su imagen de entrada) es integrable al cuadrado$f$
• suponga que su filtro conmuta con el operador de traducción , que asigna la imagen de entrada a una copia traducida de sí mismo . Un núcleo de convolución aprendido (filtro) satisface esta hipótesis.$T_t$$f$$T_t f$
• suponga que todos los filtros, no linealidades y agrupaciones en su red satisfacen una llamada condición de admisibilidad débil , que es básicamente una especie de regularidad débil y condiciones de límite. Estas condiciones son satisfechas por el núcleo de convolución aprendido (siempre y cuando se realice alguna operación de normalización en cada capa), ReLU, sigmoide, tanh, etc., no linealidades, y por agrupación promedio, pero no por agrupación máxima. Por lo tanto, cubre algunas (no todas) arquitecturas CNN del mundo real.
• Supongamos finalmente que cada capa tiene un factor de agrupación , es decir, la agrupación se aplica en cada capa y descarta efectivamente la información. La condición también sería suficiente para una versión más débil del teorema.$n$$S_n> 1$$S_n\geq 1$

Indique con la salida de la capa de la CNN, cuando la entrada es . Entonces finalmente:$\Phi^n(f)$$n$$f$

$$\lim_{n\to\infty}|||\Phi^n(T_f f)-\Phi^n(f)|||=0$$

(las barras triples no son un error), lo que básicamente significa que cada capa aprende características que se vuelven cada vez más invariables, y en el límite de una red infinitamente profunda tenemos una arquitectura perfectamente invariable. Dado que las CNN tienen un número finito de capas, no son perfectamente invariantes en la traducción, algo que los practicantes conocen bien.

Referencia: T. Wiatowski y H. Bolcskei, Una teoría matemática de redes neuronales convolucionales profundas para la extracción de características , arXiv: 1512.06293v3 .

---

Para concluir, numerosos límites para el error de generalización de una red neuronal profunda basada en su dimensión Vapnik-Chervonkensis o en la complejidad de Rademacher crecen con el número de parámetros (algunos incluso exponencialmente), lo que significa que no pueden explicar por qué los DNN funcionan tan bien en la práctica, incluso cuando el número de parámetros es considerablemente mayor que el número de muestras de entrenamiento. De hecho, la teoría VC no es muy útil en Deep Learning.

Por el contrario, algunos resultados del año pasado vinculan el error de generalización de un clasificador DNN con una cantidad que es independiente de la profundidad y el tamaño de la red neuronal, pero que depende solo de la estructura del conjunto de entrenamiento y el espacio de entrada. Bajo algunos supuestos bastante técnicos sobre el procedimiento de aprendizaje, y sobre el conjunto de entrenamiento y el espacio de entrada, pero con muy pocos supuestos sobre el DNN (en particular, los CNN están completamente cubiertos), entonces con probabilidad de al menos , tenemos$1-\delta$

$$\text{GE} \leq \sqrt{2\log{2}N_y\frac{\mathcal{N_{\gamma}}}{m}}+\sqrt{\frac{2\log{(1/\delta)}}{m}}$$

dónde:

• $\text{GE}$ es el error de generalización, definido como la diferencia entre la pérdida esperada (la pérdida promedio del clasificador aprendido en todos los puntos de prueba posibles) y la pérdida empírica (solo el error de conjunto de entrenamiento bueno)
• $N_y$ es el número de clases
• $m$ es el tamaño del conjunto de entrenamiento
• $\mathcal{N_{\gamma}}$ es el número de cobertura de los datos, una cantidad relacionada con la estructura del espacio de entrada y con la separación mínima entre puntos de diferentes clases en el conjunto de entrenamiento. Referencia:

J. Sokolic, R. Giryes, G. Sapiro y M. Rodrigues. Error de generalización de clasificadores invariantes . En AISTATS, 2017

Creo que el siguiente teorema al que te refieres se considera bastante fundamental en el aprendizaje estadístico.

Teorema (Vapnik y Chervonenkis, 1971) Sea una clase hipotética de funciones desde un dominio a y deje que la función de pérdida sea la pérdida . Entonces los siguientes son equivalentes:$H$$X$$\{0, 1\}$$0 − 1$

1. $H$ tiene la propiedad de convergencia uniforme.
2. $H$ es PAC aprendible.
3. $H$ tiene una dimensión VC finita.

Probado en una versión cuantitativa aquí:

VN Vapnik y AY 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.

La versión formulada anteriormente junto con una buena exposición de otros resultados de la teoría del aprendizaje está disponible aquí :

Shalev-Shwartz, Shai y Shai Ben-David. Comprensión del aprendizaje automático: de la teoría a los algoritmos. Cambridge University Press, 2014.

El truco del núcleo es una idea general que se usa en muchos lugares y proviene de muchas matemáticas abstractas sobre Hilbert Spaces. Demasiada teoría para que yo escriba (copie ...) en una respuesta aquí, pero si lees esto, puedes hacerte una buena idea de sus rigurosos fundamentos:

http://www.stats.ox.ac.uk/~sejdinov/teaching/atml14/Theory_2014.pdf

Mi favorita es la desigualdad de Kraft.

Teorema: para cualquier método de descripción para alfabeto finito , las longitudes de las palabras de código deben satisfacer la desigualdad .$C$$A = \{1,\dots, m\}$$L_C(1), \dots, L_C(2)$$\sum_{x \in A} 2 ^{-L_C(x)} \leq 1$

Esta desigualdad relaciona la compresión con las densidades de probabilidad : dado un código, la longitud de un resultado representado por ese código es la probabilidad de registro negativa de un modelo identificado por el código.

Además, el teorema de no almuerzo gratis para el aprendizaje automático tiene un hermano menos conocido que el teorema de no hipercompresión, que establece que no todas las secuencias se pueden comprimir.

No lo llamaría un teorema principal , pero creo que el siguiente (a veces denominado el teorema de aproximación universal) es interesante (y al menos para mí sorprendente), ya que establece el poder aproximado de las redes neuronales de avance.

Teorema: Sea una función continua no constante y monotínicamente creciente. Para cualquier función continua y cualquier , existe un entero y un perceptrón multicapa con una capa oculta que tiene neuronas que tienen como activación funcionar para que$\sigma$$f:[0,1]^m\to\mathbb{R}$$\epsilon>0$$N$$F$$N$$\sigma$

$$|F(x)-f(x)|\le\epsilon$$ para todas las .$x\in[0,1]^m$

Por supuesto, como esta es una declaración sobre la existencia , su impacto para los profesionales es insignificante.

Se puede encontrar una prueba en Hornik, Capacidades de aproximación de las redes de alimentación de multicapas, Redes neuronales 4 (2), 1991,

Aquí hay una buena publicación centrada en esta pregunta (específicamente el aprendizaje profundo en lugar de los teoremas generales de aprendizaje automático):

https://medium.com/mlreview/modern-theory-of-deep-learning-why-does-it-works-so-well-9ee1f7fb2808

Ofrece un resumen accesible de los principales teoremas emergentes para la capacidad de las redes neuronales profundas de generalizarse tan bien.