Brecha exponencial en capas de redes neuronales

Leí aquí que hay familias de funciones que necesitan nodos en la red neuronal con como máximo capas para representar la función, mientras que solo necesitan si el neural la red tiene al menos capas. Se refería a un artículo de Hastad. No lo encontré. ¿Alguien podría decirme el título del artículo? Creo que este es un resultado teórico realmente fascinante. $\mathcal{O}(2^n)$ $d - 1$ $\mathcal{O}(n)$ $d$

cc.complexity-theory reference-request jakab922
fuente

la referencia que usted cita indica que se ha comprobado para puertas lógicas, neuronas formales y FBR, y parece estar afirmando que Hastad demostró este resultado para FBR (radiales de base, "el último caso").

vzn

podría haber algo de movimiento manual aquí, la complejidad de las NN parece ser al menos tan difícil como la complejidad del circuito (pero no lo he comprobado) que todavía está llena de muchos problemas abiertos. En otros lugares, esta pregunta presentada por la coincidencia relacionada es relevante, el poder computacional de las redes neuronales tcs.se (ps, genial para ver alguna pregunta sobre el aprendizaje profundo aquí y el campo al menos tentativamente vinculado a TCS)

vzn

Respuestas:

El documento que la gente suele citar es Límites inferiores casi óptimos para circuitos de pequeña profundidad , que aparece en STOC 1986. El resultado principal de su pregunta es:

Existe una familia de funciones que admiten tamaño lineal, circuitos de profundidad (de abanico ilimitado AND / OR y NOT) que requiere un tamaño exponencial en profundidad . $k$ $k-1$

Lo que es posible aún más relevante es el hecho de que admite una separación exponencial entre la profundidad 3 y la profundidad 2 . Esto es relevante porque las puertas de umbral se usan comúnmente en redes profundas. $\mathsf{TC}^0$

Suresh Venkat
fuente

Puede ser que esto sea citado en la investigación de redes neuronales por algunos y vea la analogía básica, pero tiene referencia real / directa a las redes neuronales. para completarlo, una referencia que utilice formalmente los resultados de estos documentos dentro del marco de redes neuronales sería valiosa, si tal referencia existe.

vzn

Generalmente se cita como intuición de por qué la profundidad es importante. Creo que es un uso legítimo. Sin embargo, no es el único ejemplo de mayor profundidad que es más potente.

Suresh Venkat

@SureshVenkat ¿Hay una revisión / exposición más moderna del resultado de Hastad anterior? (Puedo ver nuevos escritos de PARITY que no están en la prueba AC ^ 0 pero no de este otro resultado en particular en el documento)

estudiante graduado

Literalmente, el problema de separar exponencialmente las redes neuronales de profundidad d de profundidad d-1, para todo d, está abierto, a lo mejor de mi conocimiento. Cuando sus "funciones de activación" son funciones de umbral lineal, por ejemplo, está abierto si todas las redes de todas las profundidades d pueden simularse, con un aumento polinómico de tamaño, en profundidad 3.

Ryan Williams
fuente

¿Tiene en mente un modelo más general de redes neuronales que o los perceptrones mencionados en las otras dos respuestas?

{T C}^{0}

$\mathsf{TC}^0$

András Salamon

Bueno, estoy hablando de circuitos compuestos por funciones de umbral lineal de profundidad constante. Eso no es más general que de profundidad constante, sin embargo, necesita una profundidad constante mayor para simular funciones de umbral lineal con . Ver Goldmann, Hastad, Razborov citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.6.1336

T C^{0}

$TC^0$

T C^{0}

$TC^0$

Ryan Williams

Estoy un poco confundido acerca de las referencias que se han dado aquí. ¿Cómo son estas redes neuronales si estas calculan funciones booleanas? ¿No estamos buscando resultados de separación para redes neuronales con activación ReLU?

R^{n} \to R

$\mathbb{R}^n \rightarrow \mathbb{R}$

gradstudent

Lea el contenido vinculado en la pregunta, no se menciona nada sobre restringir a funciones de esa forma ni las funciones de activación están restringidas a ReLU.

Ryan Williams

Sí, los leí. Pero, ¿los resultados citados aquí, como los de Hastad y otros, solo se aplican a los circuitos booleanos? El resultado de Hastad o el resultado de Goldman-Hastad-Razborov que citó: ninguno de ellos tiene ninguna implicación en las redes "reales" que son funciones con las puertas ReLU. ¿Derecha?

R^{n} \to R

$\mathbb{R}^n \rightarrow \mathbb{R}$

gradstudent

El siguiente artículo demuestra una separación exponencial de perceptrones de profundidad versus profundidad . Un perceptrón es un circuito con una sola puerta de umbral en la parte superior, y circuitos booleanos sin ventilador como entradas como entradas: $d$ $d+1$

Christer Berg, Staffan Ulfberg: un límite inferior para los perceptrones y una separación del oráculo de la . J. Comput. Syst. Sci. (JCSS) 56 (3): 263-271 (1998) $\mathsf{PP}^{\mathsf{PH}}$

Los perceptrones a menudo se denominan modelos para redes neuronales. Los autores eran estudiantes de Johan Håstad, por lo que esta podría ser la referencia que está buscando.

Jan Johannsen
fuente