¿Por qué se exagera el aprendizaje profundo a pesar de la mala dimensión de CV?

La fórmula de dimensión Vapnik – Chervonenkis (VC) para redes neuronales varía de $O(E)$ a $O(E^2)$ , con $O(E^2V^2)$ en el peor de los casos, donde $E$ es el número de aristas y $V$ es el número de nodos El número de muestras de entrenamiento necesarias para tener una fuerte garantía de generalización es lineal con la dimensión VC.

Esto significa que para una red con miles de millones de bordes, como en el caso de modelos exitosos de aprendizaje profundo, el conjunto de datos de entrenamiento necesita miles de millones de muestras de entrenamiento en el mejor de los casos, hasta miles de millones en el peor de los casos. Los conjuntos de entrenamiento más grandes actualmente tienen alrededor de cien mil millones de muestras. Dado que no hay suficientes datos de capacitación, es poco probable que los modelos de aprendizaje profundo se estén generalizando. En cambio, están sobreajustando los datos de entrenamiento. Esto significa que los modelos no funcionarán bien en datos que son diferentes a los datos de entrenamiento, lo cual es una propiedad indeseable para el aprendizaje automático.

Dada la incapacidad del aprendizaje profundo para generalizar, según el análisis dimensional de VC, ¿por qué los resultados del aprendizaje profundo son tan publicitados? El simple hecho de tener una alta precisión en algún conjunto de datos no significa mucho en sí mismo. ¿Hay algo especial en las arquitecturas de aprendizaje profundo que reduzca significativamente la dimensión VC?

Si no cree que el análisis de la dimensión VC sea relevante, proporcione evidencia / explicación de que el aprendizaje profundo está generalizando y no es demasiado adecuado. Es decir, ¿tiene buena memoria Y precisión, o solo buena memoria? El 100% de recuperación es trivial de lograr, al igual que el 100% de precisión. Acercarse a ambos al 100% es muy difícil.

Como ejemplo contrario, aquí hay evidencia de que el aprendizaje profundo es demasiado adecuado. Un modelo sobreajustado es fácil de engañar ya que ha incorporado ruido determinista / estocástico. Vea la siguiente imagen para ver un ejemplo de sobreajuste.

Además, vea las respuestas de menor rango a esta pregunta para comprender los problemas con un modelo sobreajustado a pesar de la buena precisión en los datos de la prueba.

Algunos han respondido que la regularización resuelve el problema de una gran dimensión de VC. Vea esta pregunta para mayor discusión.

"Si el mapa y el terreno no están de acuerdo, confíe en el terreno".

Realmente no se entiende por qué el aprendizaje profundo funciona tan bien como lo hace, pero ciertamente los viejos conceptos de la teoría del aprendizaje, como las dimensiones de CV, no parecen ser muy útiles.

El asunto es objeto de acalorados debates, véase, por ejemplo:

• HW Lin, M. Tegmark, D. Rolnick, ¿Por qué el aprendizaje profundo y barato funciona tan bien?
• C. Zhang, S. Bengio, M. Hardt, B. Recht, O. Vinyals, Comprender el aprendizaje profundo requiere repensar la generalización .
• D. Krueger, B. Ballas, S. Jastrzebski, D. Arpit, MS Kanwal, T. Maharaj, E. Bengio, A. Fischer, A. Courville, Deep Nets Dont Learn Via Memorization .

Con respecto al tema de los ejemplos adversos , el problema se descubrió en:

• C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, A. Rabinovich, Profundizando en convoluciones .

Se desarrolla más en:

• I. Goodfellow, J. Shlens, C. Szegedy, Explicando y aprovechando ejemplos adversarios .

Hay mucho trabajo de seguimiento.

"Dada la incapacidad del aprendizaje profundo para generalizar, según el análisis dimensional de VC [...]"

No, eso no es lo que dice el análisis dimensional VC. El análisis dimensional de VC proporciona algunas condiciones suficientes bajo las cuales se garantiza la generalización. Pero lo contrario no es necesariamente así. Incluso si no cumple con esas condiciones, el método ML aún podría generalizarse.

Dicho de otra manera: el aprendizaje profundo funciona mejor de lo que el análisis dimensional de VC lo llevaría a esperar (mejor de lo que el análisis de VC "predice"). Esa es una deficiencia del análisis dimensional de VC, no una deficiencia del aprendizaje profundo. No implica que el aprendizaje profundo sea defectuoso. Más bien, significa que no sabemos por qué funciona el aprendizaje profundo, y el análisis de VC no puede proporcionar ninguna información útil.

La alta dimensión de VC no implica que el aprendizaje profundo pueda ser engañado. La alta dimensión de VC no garantiza en absoluto si se puede engañar en situaciones prácticas. La dimensión VC proporciona un límite unidireccional, en el peor de los casos: si cumple con estas condiciones, entonces suceden cosas buenas, pero si no cumple con estas condiciones, no sabemos qué sucederá (tal vez las cosas buenas aún sucederán de todos modos, si la naturaleza se comporta mejor que el peor de los casos; el análisis de VC no promete que las cosas buenas no puedan / no sucederán).

Podría ser que la dimensión VC del espacio modelo es grande (incluye patrones muy complejos como sea posible), pero la naturaleza se explica por patrones simples, y el algoritmo ML aprende el patrón simple presente en la naturaleza (por ejemplo, debido a la regularización). - en este caso, la dimensión VC sería alta pero el modelo se generalizaría (para el patrón particular que está presente en la naturaleza).

Dicho esto ... cada vez hay más pruebas de que el aprendizaje profundo puede ser engañado por ejemplos adversos. Pero tenga cuidado con su cadena de razonamiento. Las conclusiones que está sacando no se derivan de las premisas con las que comenzó.

La gente de la industria no tiene en cuenta la dimensión VC, los gamberros ...

En una nota más seria, aunque el modelo PAC es una forma elegante de pensar sobre el aprendizaje (al menos en mi opinión), y es lo suficientemente complejo como para dar lugar a conceptos y preguntas interesantes (como la dimensión VC y su conexión con la complejidad de la muestra) , tiene muy poco que ver con situaciones de la vida real.

Recuerde que en el modelo PAC debe manejar distribuciones arbitrarias, esto significa que su algoritmo debe manejar distribuciones adversas. Al tratar de aprender algunos fenómenos en el mundo real, nadie le está dando "datos adversos" para confundir sus resultados, por lo que requerir una clase de concepto para poder aprender PAC podría ser demasiado fuerte. A veces puede vincular el error de generalización independientemente de la dimensión VC, para una clase específica de distribuciones. Este es el caso de los límites de margen, que se formulan independientemente de la dimensión VC. Pueden prometer un error de generalización bajo si puede garantizar un alto margen empírico (lo que, por supuesto, no puede suceder para todas las distribuciones, por ejemplo, tome dos puntos cercanos en el plano con etiquetas opuestas y enfoque la distribución en ellos).

Entonces, dejando a un lado el modelo PAC y la dimensión VC, creo que la exageración proviene del hecho de que parecen funcionar y tienen éxito en tareas que antes no eran posibles (uno de los últimos logros que se me viene a la mente es AlphaGo). Sé muy poco acerca de las redes neuronales, así que espero que alguien con más experiencia intervenga, pero que yo sepa todavía no hay buenas garantías (definitivamente no es como en el modelo PAC). Quizás bajo las suposiciones correctas se podría justificar formalmente el éxito de las redes neuronales (supongo que hay trabajos en torno al tratamiento formal de las redes neuronales y el "aprendizaje profundo", por lo que espero que las personas con más conocimiento sobre el tema puedan vincular algunos documentos) .

Dada la incapacidad de Deep Learning para generalizar,

No sé de dónde sacas eso. Empíricamente, la generalización se ve como la puntuación (por ejemplo, precisión) en datos no vistos.

La respuesta por la cual se usan las CNN es simple: las CNN funcionan mucho mejor que cualquier otra cosa . Vea ImageNet 2012 por ejemplo:

• CNN: 15.315% (ese fue un ejemplo temprano. Las CNN ahora están mucho mejor. Con un 4% de error de top 5)
• Mejor no CNN: 26.172% de error Top-5 ( fuente - hasta mi conocimiento, las técnicas que no usan CNN no obtuvieron menos del 25% de error top-5)

Cree un clasificador que sea mejor y la gente cambiará a eso.

ACTUALIZACIÓN: otorgaré una respuesta a cualquier persona que proporcione evidencia publicada de que el aprendizaje automático en general se engaña fácilmente, como esta evidencia para Deep Learning.

Este no es el caso. Puede crear un clasificador que sea extremadamente simple en un conjunto de datos simple. No será posible engañarlo (ni siquiera importa lo que significa "fácil"), pero tampoco es interesante.

La respuesta de una palabra es "regularización". La ingenua fórmula de dimensión VC no se aplica realmente aquí porque la regularización requiere que los pesos no sean generales. Solo una pequeña proporción (¿infinitesimal?) De combinaciones de peso tiene una pérdida aceptable después de la regularización. Como resultado, la verdadera dimensión es muchos órdenes de magnitud menos, por lo que la generalización puede ocurrir con los conjuntos de entrenamiento que tenemos. Los resultados de la vida real confirman que el sobreajuste generalmente no ocurre.

Abordamos el documento: comprender el aprendizaje profundo requiere repensar la generalización. en

Repensar la generalización requiere revisar las viejas ideas: enfoques de mecánica estadística y comportamiento de aprendizaje complejo Charles H. Martin y Michael W. Mahoney

Ver: https://arxiv.org/pdf/1710.09553.pdf

Básicamente, argumentamos que los límites de VC son demasiado flojos porque el enfoque fundamental y cómo el límite estadístico que se toma no es realista.

Un mejor enfoque radica en la Mecánica Estadística, que considera una clase de funciones dependientes de los datos, toma el límite termodinámico (no solo el límite de grandes números)

Además, también señalamos cómo las discontinuidades naturales en la profunda necesidad conducen a una transición de fase en la curva de aprendizaje, que creemos que se está observando en el documento de Google (arriba)

Con respecto a los límites, consulte la sección 4.2 de nuestro documento.

"Claramente, si arreglamos el tamaño de la muestra my dejamos que [el tamaño de la clase de función] N → ∞, [o viceversa, arreglemos N, dejemos que m → ∞] no deberíamos esperar un resultado no trivial, ya que [ N] se está volviendo más grande pero el tamaño de la muestra es fijo. Por lo tanto, [en Mecánica estadística] uno típicamente considera el caso de que m, N → ∞ tal que α = m / N es una constante fija ".

Es decir, muy raramente agregaríamos más datos (m) a una red profunda. Siempre aumentamos el tamaño de la red (N) también, porque sabemos que podemos capturar características / información más detalladas de los datos. En cambio, hacemos en la práctica lo que defendemos en el documento: tomar el límite de gran tamaño, con la relación m / N fija (en lugar de decir que se fija m y dejar que N aumente).

Estos resultados son bien conocidos en la Mecánica estadística del aprendizaje. El análisis es más complicado, pero los resultados conducen a una estructura mucho más rica que explica muchos fenómenos en el aprendizaje profundo.

Además, y en particular, se sabe que muchos límites de las estadísticas se vuelven triviales o no se aplican a distribuciones de probabilidad no uniformes, o cuando las variables toman valores discretos. Con las redes neuronales, el comportamiento no trivial surge debido a las discontinuidades (en las funciones de activación), que conducen a transiciones de fase (que surgen en el límite termodinámico).

El artículo que escribimos intenta explicar las ideas más destacadas a una audiencia de informática.

El propio Vapnik se dio cuenta de que su teoría no era realmente aplicable a las redes neuronales ... allá por 1994

"La extensión de [la dimensión VC] a las redes multicapa enfrenta [muchas] dificultades ... los algoritmos de aprendizaje existentes no pueden verse como minimizando el riesgo empírico sobre todo el conjunto de funciones implementables por la red ... [porque] es probablemente ... la búsqueda se limitará a un subconjunto de [estas] funciones ... La capacidad de este conjunto puede ser mucho menor que la capacidad de todo el conjunto ... [y] puede cambiar con el número de observaciones. Esto puede requerir una teoría que considere la noción de una capacidad no constante con un subconjunto de funciones 'activo' "
Vapnik, Levin y LeCun 1994

http://yann.lecun.com/exdb/publis/pdf/vapnik-levin-lecun-94.pdf

Si bien no es fácil de tratar con la teoría VC, este no es un problema para stat mech ... y lo que describen se parece mucho a la teoría del paisaje energético del plegamiento de proteínas. (que será el tema de un documento futuro)

Nadie parece haber señalado en las respuestas anteriores, que la fórmula de dimensión VC citada es solo para una red neuronal de 1 capa. Supongo que la dimensión VC en realidad crece exponencialmente a medida que aumenta el número de capas L. Mi razonamiento se basa en considerar las redes neuronales profundas donde la función de activación se reemplaza por otras polinómicas. Luego, el grado de los polinomios compuestos crece exponencialmente a medida que aumentan las capas.