Cálculo da dimensão VC de uma rede neural

Se eu tiver alguma topologia fixa não recorrente (DAG) (conjunto fixo de nós e arestas, mas o algoritmo de aprendizado puder variar o peso nas arestas) de neurônios sigmóides com neurônios de entrada que só podem receber cadeias em como entrada e conduz a uma saída (que gera um valor real que arredondamos para 1 ou diminuímos para -1 se estiver a um certo limite fixo longe de 0). Existe alguma maneira rápida de calcular (ou aproximar) a dimensão VC desta rede?$n$$\{-1,1\}^n$

Notas

Eu pedi uma reformulação algorítmica um pouco mais precisa no CS.SE:

Computar com eficiência ou aproximar a dimensão VC de uma rede neural

Eu tropecei em seu post enquanto procurava uma fórmula geral para calcular dimensões de VC em redes neurais, mas aparentemente não há uma. Aparentemente, temos apenas uma mistura de equações díspares de VC que só se aplicam em certos casos estreitos. Cuidado: estou baseando isso em pesquisas antigas que mal compreendo, no conceito de VC Dimensions, sobre o qual estou aprendendo apenas agora. No entanto, pode valer a pena examinar este artigo de Peter L. Bartlett e Wolfgang Maass 1no cálculo das dimensões do VC. Observe como eles se esforçam ao máximo para derivar fórmulas de VC em 13 teoremas, mas quão diversas e numerosas são as condições necessárias para cada um. Esses pré-requisitos variam desde o número de operadores nas funções de ativação até os tipos de saltos permitidos, o número de neurônios e suas posições, a profundidade de bits da entrada, etc .; existem tantas "pegadinhas" dispersas que tornam as fórmulas úteis apenas para certas classes estreitas de problemas. Para piorar a situação, eles apontam nos Teoremas 5 e 8 que funções de ativação sigmoidal são particularmente difíceis de calcular para os valores de VC. Nas páginas 6-7, eles escrevem:

"Embora a dimensão VC de redes com funções de ativação polinomial por partes seja bem compreendida, a maioria das aplicações de redes neurais usa a função sigmoide logística ou função de base radial gaussiana. Infelizmente, não é possível calcular essas funções usando um número finito de operações aritméticas listadas no Teorema 5. No entanto, Karpinski e Macintyre [Karpinski e Macintyre, 1997] estenderam o Teorema 5 para permitir o cálculo de exponenciais.A prova usa as mesmas idéias, mas o limite para o número de soluções de um sistema de equações é substancialmente mais difícil ".

Também deparei com este artigo com o título encorajador de "Dimensão VC limitada para redes neurais: progresso e perspectivas". 2Muita matemática está acima da minha cabeça e eu não a gastei o suficiente para superar minha falta de habilidades de tradução, mas suspeito que ela não oferece nenhuma solução impressionante, pois é anterior à segunda edição do livro Bartlett e Maass, que citam um trabalho posterior dos mesmos autores. Talvez pesquisas posteriores nos últimos 20 anos tenham melhorado o cálculo das dimensões de VC para redes neurais, mas a maioria das referências que encontrei parecem datar de meados dos anos 90; aparentemente, houve uma enxurrada de trabalhos sobre o assunto naquela época que desapareceu desde então. Se os recursos não foram ampliados por bolsas de estudos mais recentes, muito além do que eram nos anos 90, espero que alguém encontre uma solução mais amplamente aplicável em breve, para que eu possa começar a calcular também as dimensões de VC em minhas redes neurais. Desculpe, eu não pude

1 Bartlett, Peter L. e Maass, Wolfgang, 2003, "Dimensão Vapnik-Chervonenkis de redes neurais", pp. 1188-1192 no The Handbook of Brain Theory and Neural Networks, Arbib, Michael A. ed. Imprensa do MIT: Cambridge, Massachusetts.

2 Karpinski, Marek e Macintyre, Angus, 1995, "Dimensão VC limitada para redes neurais: progresso e perspectivas", pp. 337-341 em Proceedings of the 2nd European Conference on Computational Learning Theory, Barcelona, ​​Espanha. Vitanyi, P. ed. Notas de aula em Inteligência Artificial, nº 904. Springer: Berlin.

Aqui está o trabalho mais recente: http://jmlr.org/papers/v20/17-612.html .

Basicamente, uma rede com pesos, camadas, e activações Relu segue: para algumas constantes e .$W$$L$

Dada a validade do trabalho, acho que fornece limites úteis. Não tenho certeza, porém, do aperto dos limites (e especialmente das constantes e ), pois ainda não o li completamente.$c$$C$