¿Poder computacional de las redes neuronales?

Digamos que tenemos una red neuronal de alimentación de una sola capa con k entradas y una salida. Calcula una función a partir de , es bastante fácil ver que tiene al menos la misma potencia de cálculo que . Solo por diversión, llamaremos al conjunto de funciones computables por una red neuronal de capa única " ". $\lbrace 0,1\rbrace ^{n}\rightarrow\lbrace 0,1\rbrace$ $AC^0$ $Neural$

Parece, sin embargo, que podría tener más poder computacional que solo. $AC^0$

Así que ... es o es ? ¿También se ha estudiado este tipo de complejidad antes? $AC^0 \subseteq Neural$ $Neural = AC^0$

cc.complexity-theory circuit-complexity machine-learning ne.neural-evol gabgoh
fuente

Una nota sobre terminología: la información importante es cuántas capas ocultas hay. La red neuronal de capa oculta cero con una salida es solo una función de umbral lineal, y a menudo (confusamente) se llama red neuronal / perceptrón de una o dos capas, dependiendo de si las entradas / salidas se consideran capas. Además, en la literatura de IA, las redes neuronales se definen típicamente en términos de funciones sigmoideas, lo que significa que las entradas / salidas tienen un valor real. Se sabe que las redes de una capa oculta son aproximadores universales en el sentido de que cualquier función continua se puede aproximar arbitrariamente cerca

Yaroslav Bulatov

Respuestas:

Hay algunas referencias que podría encontrar: Cálculo de propósito general con redes neuronales: una encuesta de resultados teóricos de complejidad, 2003 y Jerarquías de conteo: tiempo polinómico y circuitos de profundidad constante, 1993 .

Parece que las redes neuronales se consideran circuitos de umbral; es decir, aquellos circuitos que usan puertas MAYORES. En (2) es el caso de que una red neuronal de profundidad tiene complejidad (aquí hay un enlace para vincular a la entrada del complejo zoológico sobre ). $d$ $TC^0_d$ $TC^0$

Dado que contiene , que es con compuertas MOD arbitrarias, entonces . Además, se menciona en el zoológico que dichos circuitos con profundidad 3 son estrictamente más potentes que los de profundidad 2. $TC^0$ $ACC^0$ $AC^0$ $AC^0 \subset TC^0$

En Sobre el poder computacional de los circuitos umbral sigmoides versus booleanos, 1991 se menciona que para una profundidad constante , los circuitos umbral booleanos y de valor real (con pesos polinomialmente limitados) son esencialmente los mismos. $d$

M. Alaggan
fuente

T C^{0}

$TC^0$