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

87

La fórmula de dimensión Vapnik – Chervonenkis (VC) para redes neuronales varía de O(E) a O(E2) , con O(E2V2) 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.

Ejemplo de ajuste, ajuste y 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.

Yters
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
DW
77
No creo que las preguntas de por qué algo "publicitado" sea bueno. La respuesta es "porque la gente". Las personas se interesan en las cosas por una gran cantidad de razones, incluido el marketing.
luk32
El aprendizaje profundo funciona en la práctica. Puede ser excesivo. Puede ser completamente injustificado. Podría estar aprendiendo secretos del universo de una deidad eldritch. Pero la exageración proviene de practicantes que de repente pueden escribir 30 líneas en el código y enseñar a una cámara a escanear firmas y unirlas con las almacenadas para validar las transacciones bancarias. O etiquete a personas desconocidas en fotografías. Etc. ¿Tal vez has escuchado la frase "no es un insulto si es verdad"? Bueno, no es exagerado si funciona. Hay muchos problemas en los que no funciona y una exageración popular excesiva. Pero funciona en la aplicación de la vida real.
Stella Biderman
La facilidad de herramientas de @StellaBiderman en torno a las técnicas estándar de aprendizaje automático es buena y todo. Pero el interés parece tener más que ver con la supuesta capacidad de aprendizaje de los DNN que tal vez rivaliza con la capacidad humana, que parece exagerarse dado el análisis VC del modelo. Una dimensión de VC tan alta implica que los modelos no se generalizarán, y en cambio están memorizando los conjuntos de datos, haciéndolos muy frágiles. Todos los ejemplos de documentos adversos parecen demostrar este punto.
yters
@gerrit No estoy seguro de que editar haya sido tan útil. Apuesto a que más personas saben qué es la dimensión VC que lo que significa.
David Richerby

Respuestas:

75

"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:

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

Se desarrolla más en:

Hay mucho trabajo de seguimiento.

Martin Berger
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
DW
Cuando dice "Hay mucho trabajo de seguimiento", ¿se refiere al último artículo de 2014? Los dos primeros documentos que menciona son bastante recientes. ¿Podría actualizar con los documentos a los que se refiere?
VF1
2
Fuerte +1 para "Si el mapa y el terreno no están de acuerdo, confía en el terreno". Los modelos funcionan extremadamente bien en la práctica, independientemente de si las matemáticas dicen que deberían hacerlo. Desde un punto de vista científico, esto sucede todo el tiempo y si algo hace que los problemas sean más interesantes. Nadie leyó el trabajo de Razborov y Rudich sobre pruebas naturales y dijo "bueno, supongo que P vs NP no es una pregunta interesante después de todo". Fueron y descubrieron que podría ser posible usar geometría algebraica para hacer teoría de la complejidad. Desde el punto de vista de la ciencia, los problemas que trascienden nuestra comprensión son mejores , no peores.
Stella Biderman
65

"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ó.

DW
fuente
66
Ω(dn)
55
-1 para "El alto VC dimensional no garantiza nada en absoluto". Esto no es cierto: una dimensión VC alta implica límites de complejidad de muestra más bajos para el aprendizaje PAC. Una buena respuesta debería abordar las distribuciones del peor de los casos frente a las distribuciones de la "vida real".
Sasho Nikolov
1
@SashoNikolov, buen punto: ¡gracias! Editado
DW
Esta publicación estaba en revisión de baja calidad. Dado el contenido, la longitud, los votos y la calidad, esto es ridículo, apuntando aquí, pero puede necesitar meta, porque algo está realmente mal.
Mal
23

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) .

Ariel
fuente
Los comentarios no son para discusión extendida; Esta conversación se ha movido al chat .
DW
15

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.

Martin Thoma
fuente
3
Un error bajo no implica generalización. Es una condición necesaria, pero no suficiente.
2017
3
@yters Defina la generalización entonces.
Martin Thoma
55
@yters, este comentario me hace pensar que no has leído mucho sobre Machine Learning. Martin dijo precisión en datos no vistos . Estás hablando de precisión en los datos de entrenamiento. Básicamente tiene razón sobre lo que es la generalización, pero tenga en cuenta que todos los demás aquí también lo entienden .
Ken Williams
1
@yters Estoy bastante seguro de que Ken (y muchas personas en este sitio, incluido yo mismo) lo sabemos. Sin embargo, si su conjunto de prueba no representa su conjunto de datos, no puede hacer ninguna declaración sobre la generalización. Si bien vale la pena tener esto en cuenta, no veo cómo esto te ayuda de ninguna manera para esta pregunta. Solo tiene que asumir / asegurarse de que su conjunto de prueba represente sus datos en el momento de la producción. De hecho, es realmente fácil demostrar que puede hacer que cualquier clasificador sea arbitrario incorrecto si las muestras de entrenamiento no representan la distribución.
Martin Thoma
2
Eso es obvio. No puede esperar que un modelo se generalice bien si está capacitado para validar los datos incorrectos. Necesita mejores datos, no un mejor modelo.
Emre
9

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.

David Khoo
fuente
2
He visto la repetida afirmación de que los resultados de la vida real muestran que el aprendizaje profundo se generaliza. ¿Cuáles son exactamente los resultados que muestran la generalización? Todo lo que he visto hasta ahora es que DL logra bajas tasas de error en conjuntos de datos particulares, lo que no significa en sí mismo que DL generalice.
yters
3
muestra buenos resultados ("bueno" = mejor que otros métodos de ML) en datos sobre los que no se entrenó . No estoy seguro de qué otra manera quiere medir prácticamente la generalización.
lvilnis
3

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)

Charles Martin
fuente
Esto suena interesante, pero no estoy seguro de seguir tu argumento. ¿Puede elaborar la primera oración, es decir, cómo el enfoque fundamental / límite estadístico es poco realista, de una manera autónoma que no requiere comprender la mecánica estadística? ¿Qué suposiciones hacen los límites de VC y por qué son poco realistas? ¿Quizás pueda editar su respuesta para incluir esa información?
DW
Agregué una referencia al trabajo original de Vapnik y LeCun (1994) que analiza el tema.
Charles Martin
Y agregó alguna aclaración.
Charles Martin
1

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.

Yan King Yin
fuente