Lacuna exponencial nas camadas da rede neural

8

Eu li aqui que existem famílias de funções que precisam de nós na rede neural com no máximo camadas para representar a função e precisam apenas de se a rede neural tiver pelo menos camadas. Referia-se a um artigo de Hastad. Eu não encontrei. Alguém poderia me dizer o título do trabalho? Eu acho que esse é um resultado teórico realmente fascinante. $\mathcal{O}(2^n)$ $d - 1$ $\mathcal{O}(n)$ $d$

cc.complexity-theory reference-request jakab922
fonte

a referência que você menciona afirma que foi comprovada para portas lógicas, neurônios formais e RBFs, e parece estar afirmando que Hastad provou esse resultado para RBFs (base radial fns, "o último caso").

vzn

pode haver alguma agitação manual aqui, a complexidade dos NNs parece ser pelo menos tão difícil quanto a complexidade do circuito (mas ainda não vi isso comprovado), que ainda está cheio de muitos problemas em aberto. em outros lugares, essa questão apresentada por uma correspondência relacionada à SE é relevante, o poder computacional das redes neurais tcs.se (ps, é ótimo ver algumas perguntas sobre aprendizado profundo aqui e no campo, pelo menos experimentalmente, ligando-se ao TCS)

vzn

9

O artigo que as pessoas costumam citar é Limites inferiores quase ótimos para pequenos circuitos de profundidade , que aparecem em STOC 1986. O principal resultado referente à sua pergunta é:

$k$ $k-1$

$\mathsf{TC}^0$

Suresh Venkat
fonte

pode ser que isso seja citado na pesquisa da rede neural por alguns e veja a analogia básica, mas tem uma referência real / direta às redes neurais. Para preenchê-lo, um árbitro que utilize formalmente os resultados deste artigo no âmbito das redes neurais seria valioso, se esse árbitro existir.

vzn

É geralmente citado como intuição por que a profundidade é importante. Eu acho que é um uso legítimo. No entanto, não é o único exemplo de maior profundidade sendo mais poderosa.

Suresh Venkat

@SureshVenkat Existe uma revisão / exposição mais moderna do resultado deste Hastad acima? (Eu posso ver novos escritos da paridade não em AC ^ 0 a prova, mas não de este particular outro resultado no papel)

gradstudent

6

Literalmente, o problema de separar exponencialmente as redes neurais de profundidade d da profundidade d-1, para todos os d, está aberto, até onde eu sei. Quando suas "funções de ativação" são funções de limite linear, por exemplo, fica aberto se todas as redes de todas as profundidades d podem ser simuladas, com um aumento polinomial de tamanho, na profundidade 3.

Ryan Williams
fonte

{T C}^{0}

$\mathsf{TC}^0$

T C^{0}

$TC^0$

T C^{0}

$TC^0$

R^{n} \to R

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

Leia o conteúdo vinculado na pergunta, não há nada mencionado sobre a restrição de funções desse formulário, nem as funções de ativação restritas à ReLU.

Ryan Williams

R^{n} \to R

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

5

$d$ $d+1$

$\mathsf{PP}^{\mathsf{PH}}$

Perceptrons são frequentemente referidos como um modelo para redes neurais. Os autores eram estudantes de Johan Håstad, então essa pode ser a referência que você está procurando.

Jan Johannsen
fonte

Lacuna exponencial nas camadas da rede neural

Respostas: